Opened 8 years ago
Closed 7 years ago
#14808 closed defect (fixed)
Permutation([1,2,3,5,4]).recoils_composition() returns [5] instead of [4, 1], and similar bugs
Reported by: | darij | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-5.12 |
Component: | combinatorics | Keywords: | combinat, permutations, days49 |
Cc: | sage-combinat | Merged in: | sage-5.12.beta0 |
Authors: | Darij Grinberg | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
sage: Permutation([1,2,3,5,4]).descents_composition() [4, 1] sage: Permutation([1,2,3,5,4]).recoils_composition() [5]
This just has to be wrong. The recoils composition of a permutation is the descent composition of its inverse; in particular, a self-inverse permutation such as [1,2,3,5,4]
should have the two compositions equal.
I think the main problem is that the actual recoils composition has its descent set formed by the values of the recoils, not the positions of the recoils. I'm fixing this in the attached patch. (This entails changing the doctest. But even with if the recoils composition would be computed using the positions rather than the values, that doctest would have been wrong.)
Wrong as well:
sage: Permutation([1,2,3]).recoils_composition() []
Also, recoils_composition
should return an actual Composition
, not just a list.
And here is my favorite permutation once again:
sage: Permutation([]).descents_composition() [0]
[0]
is not a composition.
Nothing bad about Mathworld references, but they shouldn't replace a definition, particularly if the definition given in Mathworld is confusing ( http://mathworld.wolfram.com/PermutationRun.html ).
Attached is a fix to these issues. I'm not very happy with it because the old version of recoils_composition
(once properly corrected) might have been a more interesting map than the true recoils composition -- but I can't find any reference to it under that name in literature.
Apply:
Attachments (2)
Change History (9)
comment:1 Changed 8 years ago by
- Component changed from PLEASE CHANGE to combinatorics
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Keywords days49 added
Changed 8 years ago by
comment:3 Changed 8 years ago by
- Description modified (diff)
- Reviewers set to Travis Scrimshaw
Hey Darij,
I've uploaded a new version of your patch which removed the conflicts with #14772 (this was easier than doing it in a review patch). I've also put my review changes in there, mostly some minor tweaks to the formatting to_major_code()
and recoils_composition()
docstrings. If you're happy with my changes, you can set this to positive review.
Thanks,
Travis
Apply: trac_14808-recoils_of_permutations-ts.patch
comment:4 Changed 8 years ago by
Hi Travis,
thank you; good that you caught the "returns"es (I still haven't totally internalized docstring conventions). There's only two things I want you to look at.
- In the docstring of
def PermutationOptions
, I added periods in- display: 'list' - the permutations are displayed in list notation - 'cycle' - the permutations are displayed in cycle notation
so as to delimit the different lines (otherwise, due to only single rather than double linebreak being used, they would be undelimited in the HTML output). You, however, have removed this docstring completely. Was it obsolete?
- The docstring of
def number_of_inversions
: It should say "a pair of elements(i,j)
", not "a pair of elements(p_i,p_j)
". This doesn't affect their number, but I don't want this nonstandard definition to be in the doc, particularly given that theinversions
method follows the standard definition.
comment:5 Changed 8 years ago by
- Status changed from needs_review to positive_review
comment:6 Changed 8 years ago by
comment:7 Changed 7 years ago by
- Cc changed from sage-combinat, to sage-combinat
- Merged in set to sage-5.12.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
New version up. If you are wondering why the fuss around lexicographic order being on the symmetric group which contains the permutation: there is also a lexicographic order on the *union* of all symmetric groups.