Shuffle Product

[sagetrac-elixyre]

Shuffle product can be define on any iterable object so I propose to define a new class that implement an efficient shuffle product on iterables.

Currently one has two shuffle product in Sage, one is defined on words and one is defined on permutations.

The first one is slow and don't allow to compute shuffle of two list and the second is fast but only defined for Permutations.

Some benchmarks:

My Shuffle:

Time if ShuffleProduct inherits just of SageObject

sage: from sage.combinat.shuffle import ShuffleProduct
sage: a = Word("abcdefghij")
sage: b = Word("klmnopqrst")
sage: %time _ = list(ShuffleProduct(a, b, Word))
CPU times: user 17 s, sys: 994 ms, total: 18 s
Wall time: 18.4 s

Time if ShuffleProduct inherits of the evil class Parent:

sage: from sage.combinat.shuffle import ShuffleProduct
sage: a = Word("abcdefghij")
sage: b = Word("klmnopqrst")
sage: %time _ = list(ShuffleProduct(a, b, Word))
CPU times: user 32.5 s, sys: 1.7 s, total: 34.2 s
Wall time: 34.5 s

with

Parent.__init__(self, category=FiniteEnumeratedSets())

Comparaison with ShuffleProduct_w1w2:

sage: from sage.combinat.words.shuffle_product import ShuffleProduct_w1w2 as Shuffle
sage: %time _ = list(Shuffle(a, b))
CPU times: user 59.66 s, sys: 0.29 s, total: 59.94 s
Wall time: 59.90 s

CC: @nthiery @mathzeta

Component: combinatorics

Keywords: days57

Author: Jean-Baptiste Priez

Branch/Commit: 18e97c1

Reviewer: Matthieu Dien, Tomer Bauer

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

[sagetrac-elixyre]

Branch: u/elixyre/ticket/15595

[sagetrac-git]

Commit: ade0597

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ade0597

ticket 15595

[sagetrac-git]

Changed commit from ade0597 to 9bc07b3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9bc07b3

delete a wrong test

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9730233

fast Shuffle product compatible with iterable objects (use linear extension)

[sagetrac-git]

Changed commit from 9bc07b3 to 9730233

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

24c6551	Merge branch 'shuffle/15595' into shufflee/15595
66c0f3f	trac 15595: Shuffle more efficient + some documentation + doctest

[sagetrac-git]

Changed commit from 9730233 to 66c0f3f

[sagetrac-elixyre]

Author: Jean-Baptiste Priez

[MatthieuDien]

Reviewer: MatthieuDien

[MatthieuDien]

Changed keywords from none to days57

[MatthieuDien]

Changed reviewer from MatthieuDien to Matthieu Dien

[MatthieuDien]

Changed branch from u/elixyre/ticket/15595 to u/MatthieuDien/ticket/15595

[MatthieuDien]

Changed commit from 66c0f3f to 0c59c31

[MatthieuDien]

New commits:

0c59c31

add ome documentation

[sagetrac-git]

Changed commit from 0c59c31 to b69ae60

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b69ae60

add missing '_'s

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a396edb

fix the FIXME comment

[sagetrac-git]

Changed commit from b69ae60 to a396edb

[mathzeta]

Changed reviewer from Matthieu Dien to Matthieu Dien, Tomer Bauer

[mathzeta]

Changed commit from a396edb to 68d2429

[mathzeta]

Changed branch from u/MatthieuDien/ticket/15595 to u/mathzeta2/ticket/15595

[mathzeta]

comment:18

I have added a "See also" comment to sage.combinat.words.shuffle_product.py that suggests to use the new implementation. We should open a ticket to replace and deprecated ShuffleProduct_w1w2.

[rwst]

comment:20

patchbot:

+++ b/src/sage/combinat/shuffle.py

@@ -0,0 +1,438 @@

+    a_0 \cdot \left((a_n)_{n \geqslant 1} \Cup (b_m)_{m \geqslant 0}\right)
+    + b_0 \cdot \left((a_n)_{n \geqslant 0} \Cup (b_m)_{m \geqslant 1}\right)
--- a/src/sage/combinat/words/shuffle_product.py

+++ b/src/sage/combinat/words/shuffle_product.py

@@ -1,5 +1,9 @@

Non-ascii characters inserted on 2 non-empty lines
plugins.non_ascii -- 0 seconds
========== end plugins.non_ascii ==========

[MatthieuDien]

Changed branch from u/mathzeta2/ticket/15595 to u/MatthieuDien/ticket/15595

[MatthieuDien]

Changed commit from 68d2429 to ef8433d

[MatthieuDien]

comment:22

I removed the non-ascii characters and pushed it

---

New commits:

8bf9f4e	removed non-ascii characters
b69ae60	add missing '_'s
a396edb	fix the FIXME comment
ef8433d	merge

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

18e97c1

fix underscores and contains

[sagetrac-git]

Changed commit from ef8433d to 18e97c1

[mathzeta]

comment:25

Now the tests in the file pass. Positive review!

The work never ends. From comment [comment:18]:

We should open a ticket to replace and deprecated ShuffleProduct_w1w2.

and have shuffle of variable number of iterables, and check if the Parent/Element system can be used efficiently and many other things...

[vbraun]

Changed branch from u/MatthieuDien/ticket/15595 to 18e97c1