#14808: Permutation([1,2,3,5,4]).recoils_composition() returns [5] instead of
[4,
1], and similar bugs
--------------------------------------------------+-------------------------
Reporter: darij | Owner: tbd
Type: defect | Status:
needs_review
Priority: major | Milestone: sage-5.12
Component: combinatorics | Resolution:
Keywords: combinat, permutations, days49 | Work issues:
Report Upstream: N/A | Reviewers: Travis
Scrimshaw
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------+-------------------------
Changes (by tscrim):
* reviewer: => Travis Scrimshaw
Old description:
> {{{
> 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.
New description:
{{{
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:
* [attachment:trac_14808-recoils_of_permutations-ts.patch]
--
Comment:
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,[[BR]]
Travis
Apply: trac_14808-recoils_of_permutations-ts.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14808#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
