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 tscrim)

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)

trac_14808-recoils_of_permutations-dg.patch (28.9 KB) - added by darij 8 years ago.
final version (probably)
trac_14808-recoils_of_permutations-ts.patch (26.6 KB) - added by tscrim 8 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 8 years ago by darij

  • Component changed from PLEASE CHANGE to combinatorics
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by darij

  • Keywords days49 added

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.

Changed 8 years ago by darij

final version (probably)

Changed 8 years ago by tscrim

comment:3 Changed 8 years ago by tscrim

  • 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 darij

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.

  1. 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?

  1. 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 the inversions method follows the standard definition.
Last edited 8 years ago by darij (previous) (diff)

comment:5 Changed 8 years ago by darij

  • Status changed from needs_review to positive_review

comment:6 Changed 8 years ago by tscrim

Hey Darij,

Point (1) is getting (significantly) changed in #14772, and point (2) is also getting some attention in #14772. We'll make any other (necessary) changes to the doc in there to avoid conflicts.

Best,
Travis

comment:7 Changed 7 years ago by jdemeyer

  • 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
Note: See TracTickets for help on using tickets.