# Ticket #12571(needs_work enhancement)

Opened 15 months ago

## Implementation of shifted shuffle of permutations

Reported by: Owned by: giraudo sage-combinat major sage-5.10 combinatorics Permutations; Shuffle knsam N/A Florent Hivert Samuele Giraudo #12569

### Description

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.

## Change History

### comment:1 Changed 15 months ago by giraudo

• Dependencies set to #12569

### Changed 15 months ago by giraudo

Tested on Sage 4.8, combinat branch

### comment:2 follow-up: ↓ 3 Changed 15 months ago by hivert

• Reviewers set to Florent 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

• 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

### comment:3 in reply to: ↑ 2 Changed 15 months ago by nthiery

• 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

### comment:4 Changed 15 months ago by giraudo

• Status changed from new to needs_review

### comment:5 Changed 15 months ago by giraudo

Hi Florent, hi Nicolas,

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

Samuele

### comment:6 follow-up: ↓ 7 Changed 4 months ago by elixyre

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

This post could be closed?

Jean-Baptiste

### comment:7 in reply to: ↑ 6 Changed 3 months ago by knsam

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