Implementation of shifted shuffle of permutations

[giraudo]

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.

[giraudo]

Tested on Sage 4.8, combinat branch

[hivert]

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

[nthiery]

Replying to 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

[giraudo]

Hi Florent, hi Nicolas,

thanks a lot for the suggestions of improvement. I just have updated the patch.

Samuele

[elixyre]

This patch is disappeared? I think the shuffle on words is now efficient.

This post could be closed?

Jean-Baptiste

[knsam]

Replying to 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

[ncohen]

Helloooooooooooooooooo !!!

This patch looks good 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