[Sage] #12571: Implementation of shifted shuffle of permutations
Sage
-----------------------------+----------------------------------------------
Reporter: giraudo | Owner: sage-combinat
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.0
Component: combinatorics | Keywords: Permutations; Shuffle
Work_issues: | Upstream: N/A
Reviewer: | Author: Samuele Giraudo
Merged: | Dependencies:
-----------------------------+----------------------------------------------
The shifted shuffle of two permutations can be expressed as a right
permutohedron interval. We implements a method that computes in this way
the shifted shuffle of two permutations.
Note that this improve the efficiency of the former way to compute shifted
shuffle of permutations:
{{{
sage: p1 = Permutations(10).random_element()
sage: p2 = Permutations(7).random_element()
}}}
{{{
sage: _ = [Permutation(p) for p in Word(p1).shifted_shuffle(Word(p2))]
}}}
takes about 19.95 s CPU time on my computer, but
{{{
sage: _ = p1.shifted_shuffle(p2)
}}}
takes about 3.94 s CPU time.
We also implements Loday-Ronco's over and under operations on
permutations.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB
Sage
-----------------------------+----------------------------------------------
Reporter: giraudo | Owner: sage-combinat
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.0
Component: combinatorics | Keywords: Permutations; Shuffle
Work_issues: | Upstream: N/A
Reviewer: | Author: Samuele Giraudo
-----------------------------+----------------------------------------------
Changes (by giraudo):
* dependencies: => #12569
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:1>
Sage
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.0
Component: combinatorics | Keywords: Permutations; Shuffle
Work_issues: | Upstream: N/A
Merged: | Dependencies: #12569
------------------------------+---------------------------------------------
Changes (by hivert):
* reviewer: => Florent Hivert
Comment:
Hi Samuele,
Good to have you onboard !
- First of all, if you want a review you should check the {{{needs-
review}}} button below.
- when you put some example under the title {{{EXAMPLES::}}}
there is no need to but them in {{{TESTS::}}}. Both are tested alike.
- You should add a rubric {{{INPUT::}}} explaining what {{{other}}} can
be. Here I think it could be a {{{Permutations}}}, a {{{list}}}, a
{{{tuple}}}
or any {{{iterable}}}. A few examples demonstrating this should also be
added
(see
[http://www.sagemath.org/doc/developer/conventions.html#documentation-
strings documentation strings] for the precise syntax).
- Are you sure that you didn't mixed up the convention for over/under ? To
break the ambiguity, I'd rather call them {{{shifted_concatenation}}} and
{{{shifted_anti_concatenation}}}. Or maybe only one function
{{{shifted_concatenation}}}, with an optional parameter {{{shift}}} which
can
be either {{{"left"}}} or {{{"right"}}}. Or even
{{{shift_right (True by default)}}}...
What do you think ? Maybe it is worth asking for a vote on
{{{Sage-combinat-devel}}}.
- You should add a ".. SEEALSO::" rubric linking the three functions one
to
the other (see also #12078 ;-)
- Finally, You could add some consistency tests checking that for some
relatively large permutations, the cardinality of the interval in the
correct
binomial coefficient.
Sorry for this long list of requests, once you gets used to Sage, you'll
do all
of this without thinking of it.
And many thanks for taking care of this.
Florent
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:2>
Sage
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.0
Component: combinatorics | Keywords: Permutations; Shuffle
Work_issues: | Upstream: N/A
Merged: | Dependencies: #12569
------------------------------+---------------------------------------------
Comment(by nthiery):
Replying to [comment:2 hivert]:
> - Are you sure that you didn't mixed up the convention for over/under ?
To
> break the ambiguity, I'd rather call them {{{shifted_concatenation}}}
and
> {{{shifted_anti_concatenation}}}. Or maybe only one function
> {{{shifted_concatenation}}}, with an optional parameter {{{shift}}}
which can
> be either {{{"left"}}} or {{{"right"}}}. Or even
> {{{shift_right (True by default)}}}...
Quite a few functions take an argument side="left"/"right", more often
than not the default being "right". If
{{{
x.shifted_concatenation(y, side="right")
}}}
sounds unambiguous enough about the shift being on y (and not the
concatenation being on the right), I vote for this. Otherwise
shift="left"/"right"
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:3>
Sage
Reporter: giraudo | Owner: sage-combinat
Type: enhancement | Status: needs_review
Component: combinatorics | Keywords: Permutations; Shuffle
Work_issues: | Upstream: N/A
Merged: | Dependencies: #12569
------------------------------+---------------------------------------------
Changes (by giraudo):
* status: new => needs_review
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:4>
Sage
Reporter: giraudo | Owner: sage-combinat
Type: enhancement | Status: needs_review
Component: combinatorics | Keywords: Permutations; Shuffle
Work_issues: | Upstream: N/A
Merged: | Dependencies: #12569
------------------------------+---------------------------------------------
Comment(by giraudo):
Hi Florent, hi Nicolas,
thanks a lot for the suggestions of improvement. I just have updated the
patch.
Samuele
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:5>
Sage
Reporter: giraudo | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.6
Component: combinatorics | Resolution:
Keywords: Permutations; Shuffle | Work issues:
Report Upstream: N/A | Reviewers: Florent Hivert
Authors: Samuele Giraudo | Merged in:
Dependencies: #12569 | Stopgaps:
-----------------------------------------+----------------------------------
Comment (by elixyre):
This patch is disappeared? I think the shuffle on words is now efficient.
This post could be closed?
Jean-Baptiste
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:6>
Sage
Reporter: giraudo | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.7
Keywords: Permutations; Shuffle | Work issues:
Report Upstream: N/A | Reviewers: Florent Hivert
Authors: Samuele Giraudo | Merged in:
Dependencies: #12569 | Stopgaps:
-----------------------------------------+----------------------------------
Comment (by knsam):
Replying to [comment:6 elixyre]:
> This patch is disappeared? I think the shuffle on words is now
efficient.
Not quite. Sage 5.6 takes 21.93 seconds.
>
> This post could be closed?
So, no I'd think.
>
> Jean-Baptiste
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:7>
Sage
Reporter: giraudo | Owner: sage-combinat
Priority: major | Milestone: sage-5.7
Component: combinatorics | Resolution:
Keywords: Permutations; Shuffle | Work issues:
Report Upstream: N/A | Reviewers: Florent Hivert
Authors: Samuele Giraudo | Merged in:
Dependencies: #12569 | Stopgaps:
-----------------------------------------+----------------------------------
* cc: knsam (added)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:8>
Sage
Reporter: giraudo | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.8
Keywords: Permutations; Shuffle | Work issues:
Report Upstream: N/A | Reviewers: Florent Hivert
Authors: Samuele Giraudo | Merged in:
Dependencies: #12569 | Stopgaps:
-----------------------------------------+----------------------------------
* status: needs_review => needs_work
Comment:
Helloooooooooooooooooo !!!
This patch looks ood to go, but it would be nice to add your two new
methods to the (new) index of methods at the top of permutation.py `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:9>
Sage
Reporter: giraudo | Owner: sage-combinat
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-5.11
Keywords: Permutations; Shuffle | Work issues:
-----------------------------------------+----------------------------------
Changes (by darij):
* status: needs_work => positive_review
* reviewer: Florent Hivert => Florent Hivert, Darij Grinberg
* dependencies: #12569 => #12569, #14772
Comment:
Methods added to the index. Patch reviewed and rebased upon #14772.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:10>
Sage
Reporter: giraudo | Owner: sage-combinat
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Keywords: Permutations; Shuffle | Work issues:
Report Upstream: N/A | Reviewers: Florent Hivert, Darij Grinberg
Authors: Samuele Giraudo | Merged in:
Dependencies: #12569, #14772 | Stopgaps:
-----------------------------------------+----------------------------------
Changes (by darij):
* cc: tscrim, sage-combinat (added)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12571#comment:11>