Implementation of shifted shuffle of permutations

[SamueleGiraudo]

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.

Depends on #12569
Depends on #14772
Depends on #8386
Depends on #14519
Depends on #14808
Depends on #14143
Depends on #14015
Depends on #14516

CC: @KPanComputes @tscrim @sagetrac-sage-combinat

Component: combinatorics

Keywords: Permutations, Shuffle

Author: Samuele Giraudo

Reviewer: Florent Hivert, Darij Grinberg

Merged: sage-5.12.beta5

Issue created by migration from https://trac.sagemath.org/ticket/12571

[SamueleGiraudo]

Dependencies: #12569

[hivert]

Reviewer: Florent Hivert

[hivert]

comment:2

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 Add an example of SEE ALSO section in the dev-guide #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]

comment:3

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

[SamueleGiraudo]

comment:5

Hi Florent, hi Nicolas,

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

Samuele

[sagetrac-elixyre]

comment:6

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

This post could be closed?

Jean-Baptiste

[KPanComputes]

comment:7

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

[nathanncohen]

comment:9

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

[darijgr]

Changed dependencies from #12569 to #12569, #14772

[darijgr]

comment:10

Methods added to the index. Patch reviewed and rebased upon #14772.

[darijgr]

Changed reviewer from Florent Hivert to Florent Hivert, Darij Grinberg

[jdemeyer]

Changed dependencies from #12569, #14772 to #12569, #14772, #8386, #14519, #14808, #14143, #14015, #14516

[jdemeyer]

comment:15

The documentation has problems:

dochtml.log:[combinat ] /mazur/release/merger/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/combinat/permutation.py:docstring of sage.combinat.permutation:5: WARNING: Bullet list ends without a blank line; unexpected unindent.

[darijgr]

Attachment: trac_12571-shifted_shuffle_of_permutations-reviewed.patch.gz

reviewed version, qfolded with the patch so as to avoid fuzz when applying the old patch after #14772. I added some more doctests and docstring text. Now rebased upon current version of #14772. Now with fixed docstring.

[darijgr]

comment:16

Good point. There was an INPUT item split across two lines, and the second line was not indented to the same level as the first. I assume this was obvious enough to revert to positive_review.

[jdemeyer]

Merged: sage-5.12.beta5