Opened 6 years ago
Closed 6 years ago
#20555 closed enhancement (fixed)
descents for Permutations : cleanup
Reported by:  chapoton  Owned by:  

Priority:  major  Milestone:  sage7.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: 
Description (last modified by )
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
 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
comment:2 Changed 6 years ago by
 Commit changed from b2f952ac34d40ac79e695363b28463ce8f92cf40 to e8d4c22b1991ffc181022e05820e3de50d1d30a5
Branch pushed to git repo; I updated commit sha1. New commits:
e8d4c22  more doc for descents in permutation

comment:3 Changed 6 years ago by
 Cc nthiery. stumpc5 added; nthiery removed
comment:4 Changed 6 years ago by
 Cc nthiery added; nthiery. removed
comment:5 Changed 6 years ago by
 Commit changed from e8d4c22b1991ffc181022e05820e3de50d1d30a5 to e6393ab4a5bc9917a95a7e472452548eeed33ddd
Branch pushed to git repo; I updated commit sha1. New commits:
e6393ab  trac 20555 fixing doctests in the rest of sage

comment:6 Changed 6 years ago by
There is a (very) good reason for descents of permutations to be 0based indices: they correspond to the positions in the list, which are also 0based, 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 0based, 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
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:
 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.
 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 oneline 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.)
comment:8 Changed 6 years ago by
(only now seeing that Travis also answered similarly some secs earlier...)
comment:9 Changed 6 years ago by
 Commit changed from e6393ab4a5bc9917a95a7e472452548eeed33ddd to 7797062c90e16874eb524ca42da0d795fa9548b6
Branch pushed to git repo; I updated commit sha1. New commits:
7797062  introducing a parameter from_zero in descents of permutations (step1)

comment:10 Changed 6 years ago by
 Commit changed from 7797062c90e16874eb524ca42da0d795fa9548b6 to 0841782343a68d0e2ae150062a9bcc8eb469a049
Branch pushed to git repo; I updated commit sha1. New commits:
0841782  trac 20555 adjustement to new keyword from_zero in descents

comment:11 Changed 6 years ago by
 Commit changed from 0841782343a68d0e2ae150062a9bcc8eb469a049 to 6abfeaa8061791dcd8e2ce7066388d39e57ca0e2
comment:12 Changed 6 years ago by
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 userfriendly, 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
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
 Commit changed from 6abfeaa8061791dcd8e2ce7066388d39e57ca0e2 to 80b6546d726de6bda3feca619b4b6599d18cbf3e
Branch pushed to git repo; I updated commit sha1. New commits:
80b6546  trac 20555 adding a deprecation warning for descents starting at 0

comment:15 Changed 6 years ago by
 Commit changed from 80b6546d726de6bda3feca619b4b6599d18cbf3e to 12472e04b273d8b0c54e9e2209d69d037d927486
Branch pushed to git repo; I updated commit sha1. New commits:
12472e0  trac 20555 fixing doctests in braid group

comment:16 Changed 6 years ago by
ok, patchbot is green, and ticket ready for review
comment:17 Changed 6 years ago by
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 thefinal_descent
flag?
comment:18 Changed 6 years ago by
 Commit changed from 12472e04b273d8b0c54e9e2209d69d037d927486 to 0e1c23bc2d7326980c1970e7fc0fcb379a629f78
Branch pushed to git repo; I updated commit sha1. New commits:
0e1c23b  trac 20555 reviewer's comments

comment:19 Changed 6 years ago by
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
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
 Reviewers set to Christian Stump, Travis Scrimshaw
comment:22 Changed 6 years ago by
 Reviewers changed from Christian Stump, Travis Scrimshaw to Travis Scrimshaw, Christian Stump
comment:23 Changed 6 years ago by
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
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
bot is green.
comment:26 followup: ↓ 28 Changed 6 years ago by
Sorry for the delay in my comments. Here they are:
 I think it is better to use the more explicit
tester.assertEqual
andtester.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:
Similarly for
INPUT:   ``final_descent``  optional boolean (default ``False``)  If ``True``, the last position of a nonempty  permutation is also considered as a descent. +  ``final_descent``  boolean (default ``False``); + if ``True``, the last position of a nonempty + 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`
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 0based 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 sagedevel and this deprecation, the migration should be smooth.
comment:27 Changed 6 years ago by
 Commit changed from 0e1c23bc2d7326980c1970e7fc0fcb379a629f78 to 8dc44205ed34a559df49aa24ddd14facf47a7b0e
Branch pushed to git repo; I updated commit sha1. New commits:
8dc4420  trac 20555 changes after some of the reviewer's comments

comment:28 in reply to: ↑ 26 ; followup: ↓ 29 Changed 6 years ago by
Replying to tscrim:
As a counterpoint, the (very) good reasons that descents start at 0 is because Python uses 0based indexing:
sage: p = Permutation([5,3,2,4,1]) sage: p.descents() [0, 1, 3] sage: p[0] 5This 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 oneline notation, or the first cycle in cycle decomposition, or whatever else, depending on the implementation of permutations) and not a mathematically welldefined operation. In my eyes, the mathematical operation is
sage: p(1) 5
which matches Frédéric's indexing.
comment:29 in reply to: ↑ 28 ; followup: ↓ 31 Changed 6 years ago by
Replying to stumpc5:
Replying to tscrim: I would consider
p[0]
an implementation detail (as this might mean something in oneline notation, or the first cycle in cycle decomposition, or whatever else, depending on the implementation of permutations) and not a mathematically welldefined operation. In my eyes, the mathematical operation issage: p(1) 5which 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 (p_{0}, p_{1}, ..., p_{n1}), then p[i]
corresponds to p_{i}. 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
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
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 (p_{0}, p_{1}, ..., p_{n1}), then
p[i]
corresponds to p_{i}. 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,...,n1}, and the list just to be oneline 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,...,n1}, 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,...,n1} 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
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
 Commit changed from 8dc44205ed34a559df49aa24ddd14facf47a7b0e to d1d42eb9f6ae7599d5f755ba65998613b64c4503
comment:34 Changed 6 years ago by
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
This LGTM. Christian?
comment:36 Changed 6 years ago by
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
None is a technical detail. It does indeed default to True
comment:38 Changed 6 years ago by
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
 Status changed from needs_review to positive_review
Well, okay then...
comment:40 Changed 6 years ago by
 Branch changed from u/chapoton/20555 to d1d42eb9f6ae7599d5f755ba65998613b64c4503
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
cleanup the behaviour of descents in Permutations + add tests in TestSuite