Opened 6 years ago

Closed 6 years ago

#20555 closed enhancement (fixed)

descents for Permutations : cleanup

Reported by: chapoton Owned by:
Priority: major Milestone: sage-7.2
Component: combinatorics Keywords: permutation
Cc: hivert, tscrim, darij, nthiery, stumpc5 Merged in:
Authors: Frédéric Chapoton Reviewers: Travis Scrimshaw, Christian Stump
Report Upstream: N/A Work issues:
Branch: d1d42eb (Commits, GitHub, GitLab) Commit: d1d42eb9f6ae7599d5f755ba65998613b64c4503
Dependencies: Stopgaps:

Status badges

Description (last modified by chapoton)

The descents in class Permutation need a little care to behave like the other Coxeter groups. Let us do that.

As a benefit, the descents will now follow the usual combinatorics convention (instead of a wrong indexing starting at 0).

Plus adding a new test about descents in the TestSuite? of Coxeter groups.

This is useful for future uniform implementation of some new posets.

Change History (40)

comment:1 Changed 6 years ago by chapoton

  • Branch set to u/chapoton/20555
  • Cc hivert tscrim darij nthiery added
  • Commit set to b2f952ac34d40ac79e695363b28463ce8f92cf40
  • Description modified (diff)
  • Keywords permutation added
  • Status changed from new to needs_review

New commits:

b2f952acleanup the behaviour of descents in Permutations + add tests in TestSuite

comment:2 Changed 6 years ago by git

  • Commit changed from b2f952ac34d40ac79e695363b28463ce8f92cf40 to e8d4c22b1991ffc181022e05820e3de50d1d30a5

Branch pushed to git repo; I updated commit sha1. New commits:

e8d4c22more doc for descents in permutation

comment:3 Changed 6 years ago by chapoton

  • Cc nthiery. stumpc5 added; nthiery removed

comment:4 Changed 6 years ago by chapoton

  • Cc nthiery added; nthiery. removed

comment:5 Changed 6 years ago by git

  • Commit changed from e8d4c22b1991ffc181022e05820e3de50d1d30a5 to e6393ab4a5bc9917a95a7e472452548eeed33ddd

Branch pushed to git repo; I updated commit sha1. New commits:

e6393abtrac 20555 fixing doctests in the rest of sage

comment:6 Changed 6 years ago by tscrim

There is a (very) good reason for descents of permutations to be 0-based indices: they correspond to the positions in the list, which are also 0-based, where there is a descent. This is also a perfectly valid definition and almost certainly corresponds to the initial definition of a descent. Personally I am for switching the descents convention, but this is a major backwards incompatible change that is highly likely to break personal code. Also there will not be deprecation period. Much care must be taken here.

A possible way to introduce a deprecation would be to have an optional argument to descents for being 0-based, which is True by default. If this argument is True, then we print a deprecation warning. At the very least, this requires a posting of sage(-combinat)-devel notifying of the behavior change.

comment:7 Changed 6 years ago by stumpc5

I am personally not totally convinced that this change is the right way to go - I think it is a typical example that it is simply very hard to make notions that are consistent all over sage:

  1. Let w be a finite word in a totally ordered alphabet,say {1,...,n}. Its descents are the positions i such that w_i > w_{i+1}. Since python indexes words (or rather lists/tuples) starting with 0, it is natural to write w = w_0 w_1 ... w_m.
  1. Let w be a permutation of {1,...,n}. A descent of w is an index i such that w*(i i+1) ls weak order smaller than w. But on the other hand, its one-line notation is a word, it inherits the notion of descents from above, which now differs in a shift by 1.

(There are tons of other examples already in the combinatorics part of sage, and the category framework makes that *really* hard to properly organize imho.)

Last edited 6 years ago by stumpc5 (previous) (diff)

comment:8 Changed 6 years ago by stumpc5

(only now seeing that Travis also answered similarly some secs earlier...)

comment:9 Changed 6 years ago by git

  • Commit changed from e6393ab4a5bc9917a95a7e472452548eeed33ddd to 7797062c90e16874eb524ca42da0d795fa9548b6

Branch pushed to git repo; I updated commit sha1. New commits:

7797062introducing a parameter from_zero in descents of permutations (step1)

comment:10 Changed 6 years ago by git

  • Commit changed from 7797062c90e16874eb524ca42da0d795fa9548b6 to 0841782343a68d0e2ae150062a9bcc8eb469a049

Branch pushed to git repo; I updated commit sha1. New commits:

0841782trac 20555 adjustement to new keyword from_zero in descents

comment:11 Changed 6 years ago by git

  • Commit changed from 0841782343a68d0e2ae150062a9bcc8eb469a049 to 6abfeaa8061791dcd8e2ce7066388d39e57ca0e2

Branch pushed to git repo; I updated commit sha1. New commits:

a066912Merge branch 'u/chapoton/20555' into 7.2.rc1
6abfeaafixing trivially failing doctests

comment:12 Changed 6 years ago by chapoton

ok, guys. I have added a from_zero argument in the descents of permutations.

Given that our permutations are indexed by 1,...,n, I really think that there is no good reason to have the descents starting at 0. But of course, one need to be user-friendly, so let us for the moment just prepare for this change.

The branch would work if I disactivate the test for descents in the testsuites for permutations.

I propose to do that, and also to add a deprecation when using from_zero=True even if it looks rather strange to me to do that for a default value of the argument.

Any comments ?

comment:13 Changed 6 years ago by stumpc5

There are now a few testsuite failures. Beside from that, I am okay with the new procedure to handle the descents in permutations.

comment:14 Changed 6 years ago by git

  • Commit changed from 6abfeaa8061791dcd8e2ce7066388d39e57ca0e2 to 80b6546d726de6bda3feca619b4b6599d18cbf3e

Branch pushed to git repo; I updated commit sha1. New commits:

80b6546trac 20555 adding a deprecation warning for descents starting at 0

comment:15 Changed 6 years ago by git

  • Commit changed from 80b6546d726de6bda3feca619b4b6599d18cbf3e to 12472e04b273d8b0c54e9e2209d69d037d927486

Branch pushed to git repo; I updated commit sha1. New commits:

12472e0trac 20555 fixing doctests in braid group

comment:16 Changed 6 years ago by chapoton

ok, patchbot is green, and ticket ready for review

comment:17 Changed 6 years ago by stumpc5

A few minor questions:

+            for i in self.index_set():
+                si = s[i]
+                tester.assert_(i in si.descents(side='left'))
+                tester.assert_(i in si.descents(side='right'))
+                tester.assert_(i not in si.descents(positive=True, side='left'))
+                tester.assert_(i not in si.descents(positive=True, side='right'))
  • Is it correct to test self.index_set, which could in principle be different from {1,...,n}?
  • You could possibly be even more specific on the assertions, such as [i] == si.descents(side='left').
+ d = [0] + self.descents(from_zero=False) + [len(self)]
  • Isn't this + [len(self)] exactly the final_descent flag?

comment:18 Changed 6 years ago by git

  • Commit changed from 12472e04b273d8b0c54e9e2209d69d037d927486 to 0e1c23bc2d7326980c1970e7fc0fcb379a629f78

Branch pushed to git repo; I updated commit sha1. New commits:

0e1c23btrac 20555 reviewer's comments

comment:19 Changed 6 years ago by chapoton

Thanks for having a look.

I do not understand you first point.

I changed the second point, but now we need to wait and see if the patchbot is still green.

I changed the third point too.

comment:20 Changed 6 years ago by stumpc5

I do not understand you first point.

Maybe I misunderstand the tester, but isn't this test supposed to pass always? What if I use index_set = ['A','B','C'], would it still pass then with this test?

tester.assert_(i not in si.descents(positive=True, side='left'))
tester.assert_(i not in si.descents(positive=True, side='right'))

If you want, you could be also explicit in those tests.

Beside those two points, I give it a positive review given the patchbot turns green.

comment:21 Changed 6 years ago by stumpc5

  • Reviewers set to Christian Stump, Travis Scrimshaw

comment:22 Changed 6 years ago by stumpc5

  • Reviewers changed from Christian Stump, Travis Scrimshaw to Travis Scrimshaw, Christian Stump

comment:23 Changed 6 years ago by chapoton

Concerning the first point, the very same kind of loop over self.index_set is already used in the similar method test_has_descent just above in the code. So in general I think we do expect descents to be elements of the index set.

Concerning the second point, should I really change that ? I would prefer not to.

comment:24 Changed 6 years ago by stumpc5

So in general I think we do expect descents to be elements of the index set.

I see, I was actually missing this point before.

Concerning the second point, should I really change that ? I would prefer not to.

Okay, your decision.

Waiting for the patchbot, and also for Travis' okay...

comment:25 Changed 6 years ago by chapoton

bot is green.

comment:26 follow-up: Changed 6 years ago by tscrim

Sorry for the delay in my comments. Here they are:

  • I think it is better to use the more explicit tester.assertEqual and tester.assertNotIn (they have better default error messages).
  • You also need to have some sort of warning message saying that the behavior of ParkingFunction.ides has changed.
  • Some docstring changes:
             INPUT:
     
    -        - ``final_descent`` -- optional boolean (default ``False``)
    -          If ``True``, the last position of a non-empty
    -          permutation is also considered as a descent.
    +        - ``final_descent`` -- boolean (default ``False``);
    +          if ``True``, the last position of a non-empty
    +          permutation is also considered as a descent
     
    -        - ``side`` -- optional, ``'right'`` (default) or ``'left'``
    -          If ``'left'``, return the descents of the inverse permutation.
    +        - ``side`` -- ``'right'`` (default) or ``'left'``;
    +          if ``'left'``, return the descents of the inverse permutation
     
    -        - ``positive`` -- optional boolean (default ``False``)
    -          If ``True``, return the positions that are not descents.
    +        - ``positive`` -- boolean (default ``False``);
    +          if ``True``, return the positions that are not descents
     
    -        - ``from_zero`` -- optional boolean (default ``True``)
    -          If ``False``, return the positions starting from `1`
    +        - ``from_zero`` -- boolean (default ``True``);
    +          if ``False``, return the positions starting from `1`
    
    Similarly for idescents.
  • Your deprecation message does not match the docstring. If from_zero is going to be removed, we should explicitly state in that in the docstring. Also the default behavior either will change or this argument should not be deprecated.

As a counterpoint, the (very) good reasons that descents start at 0 is because Python uses 0-based indexing:

sage: p = Permutation([5,3,2,4,1])
sage: p.descents()
[0, 1, 3]
sage: p[0]
5

This would break this behavior with the current branch, and actually, thinking a bit more now about it, we should add some documentation to this point. (I am pretty sure the position of the descent must correspond to the position of the larger value for the related math to work, but it's been awhile since I've thought about these things.)

However, I think with sufficient advertising on sage-devel and this deprecation, the migration should be smooth.

comment:27 Changed 6 years ago by git

  • Commit changed from 0e1c23bc2d7326980c1970e7fc0fcb379a629f78 to 8dc44205ed34a559df49aa24ddd14facf47a7b0e

Branch pushed to git repo; I updated commit sha1. New commits:

8dc4420trac 20555 changes after some of the reviewer's comments

comment:28 in reply to: ↑ 26 ; follow-up: Changed 6 years ago by stumpc5

Replying to tscrim:

As a counterpoint, the (very) good reasons that descents start at 0 is because Python uses 0-based indexing:

sage: p = Permutation([5,3,2,4,1])
sage: p.descents()
[0, 1, 3]
sage: p[0]
5

This would break this behavior with the current branch, and actually, thinking a bit more now about it, we should add some documentation to this point. (I am pretty sure the position of the descent must correspond to the position of the larger value for the related math to work, but it's been awhile since I've thought about these things.)

I do totally agree with the math part. But I am less convinced of the sage part:

sage: p = Permutation([5,3,2,4,1])
sage: p[0]
5

I would consider p[0] an implementation detail (as this might mean something in one-line notation, or the first cycle in cycle decomposition, or whatever else, depending on the implementation of permutations) and not a mathematically well-defined operation. In my eyes, the mathematical operation is

sage: p(1)
5

which matches Frédéric's indexing.

Last edited 6 years ago by stumpc5 (previous) (diff)

comment:29 in reply to: ↑ 28 ; follow-up: Changed 6 years ago by tscrim

Replying to stumpc5:

Replying to tscrim: I would consider p[0] an implementation detail (as this might mean something in one-line notation, or the first cycle in cycle decomposition, or whatever else, depending on the implementation of permutations) and not a mathematically well-defined operation. In my eyes, the mathematical operation is

sage: p(1)
5

which matches Frédéric's indexing.

If you think of the permutation as an automorphism of [n], yes, but if you think of it as an ordering of [n] written as (p0, p1, ..., pn-1), then p[i] corresponds to pi. So it is a little more than an implementation detail. Moreover, this perspective makes the descent set independent of the index set and/or the objects we are permuting.

Also, what is both of your opinions on removing the from_zero option or just changing the default?

@chapoton Thanks for the changes.

comment:30 Changed 6 years ago by chapoton

I would rather just change the default value of from_zero, after one year of deprecation.

comment:31 in reply to: ↑ 29 Changed 6 years ago by stumpc5

Replying to tscrim:

If you think of the permutation as an automorphism of [n], yes, but if you think of it as an ordering of [n] written as (p0, p1, ..., pn-1), then p[i] corresponds to pi. So it is a little more than an implementation detail. Moreover, this perspective makes the descent set independent of the index set and/or the objects we are permuting.

A priori, one could consider the list [Travis,Frédéric,Christian] a permutation, but one cannot multiply such permutations (in contrary to permutations in Sage). I think, you implicitly expect the objects to be totally ordered (that is actually also needed to define descents in the first place) and indeed in bijection with {1,...,n} or {0,...,n-1}, and the list just to be one-line notation for the bijection.

I more believe our "argument" is closer to the surface: it is mathematically more common to start labelling with 1, so it was decided to have permutations of {1,...,n} per default instead of {0,...,n-1}, and it is pythonically more common to start labelling with 0. These two handmade choices conflict whenever they meet in the code, and one has to choose one over the other to go on.

Indeed, I think it would have been better to make permutations on {0,...,n-1} standard, and as well indexing sets. This would

  • have generally not resulted in the above conflict,
  • result in many speed improvements everywhere, see
    sage: %timeit p[0]
    1000000 loops, best of 3: 610 ns per loop
    sage: %timeit p(1)
    100000 loops, best of 3: 2.74 µs per loop
    
  • cleaner code as one does not always need to do the +1/-1 thing for lookups (see the code on reflection groups).

But that choice is made and not reversible, so we have to argue what to do whenever we see that conflict appearing.

Also, what is both of your opinions on removing the from_zero option or just changing the default?

I do not have a strong opinion there, both choices have their rights to be taken. If I'd do it myself, I would maybe leave the option and make it from_one per default. (I would also make the name of the option the default behaviour, don't you think so?)

comment:32 Changed 6 years ago by tscrim

Since we are only wanting to change the default behavior, we should have the default value be None (not necessarily changing the doc), where we emit the deprecation warning in this case. That way when someone explicitly passes True, they don't needlessly see the deprecation warning (as their code will correctly work once we change the default behavior).

Also, do we want to call the option from_zero or from_one? It is better to make that decision here.

comment:33 Changed 6 years ago by git

  • Commit changed from 8dc44205ed34a559df49aa24ddd14facf47a7b0e to d1d42eb9f6ae7599d5f755ba65998613b64c4503

Branch pushed to git repo; I updated commit sha1. New commits:

4c1be01Merge branch 'u/chapoton/20555' into 7.2.rc2
d1d42ebtrac 20555 in descents of permutations, use None as default for from_zero

comment:34 Changed 6 years ago by chapoton

I would rather keep from_zero. After the change of default value, it will be the best name in my opinion.

comment:35 Changed 6 years ago by tscrim

This LGTM. Christian?

comment:36 Changed 6 years ago by stumpc5

I still see one ``from_zero`` -- boolean (default ``True``) which should be (default ``None``) and don't have a computer currently to change it. Beside that, it's good to go I think.

comment:37 Changed 6 years ago by chapoton

None is a technical detail. It does indeed default to True

comment:38 Changed 6 years ago by tscrim

The default "is" True, it's just we need the actual to be None for technical reasons (the deprecation warning).

comment:39 Changed 6 years ago by stumpc5

  • Status changed from needs_review to positive_review

Well, okay then...

comment:40 Changed 6 years ago by vbraun

  • Branch changed from u/chapoton/20555 to d1d42eb9f6ae7599d5f755ba65998613b64c4503
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.