Shuffle product of iterables

The shuffle product of two sequences of lengths \(m\) and \(n\) is a sum over the \(\binom{m+n}{n}\) ways of interleaving the two sequences.

That could be defined inductively by:

\[(a_n)_{n \geqslant 0} \Cup (b_m)_{m \geqslant 0} = 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)\]

with \((a_n)\) and \((b_m)\) two non-empty sequences and if one of them is empty then the product is equals to the other.

The shuffle product has been introduced by S. Eilenberg and S. Mac Lane in 1953 [EilLan53].

EXAMPLES:

sage: from sage.combinat.shuffle import ShuffleProduct
sage: list(ShuffleProduct([1,2], ["a", "b", "c"]))
[[1, 2, 'a', 'b', 'c'],
 ['a', 1, 2, 'b', 'c'],
 [1, 'a', 2, 'b', 'c'],
 ['a', 'b', 1, 2, 'c'],
 ['a', 1, 'b', 2, 'c'],
 [1, 'a', 'b', 2, 'c'],
 ['a', 'b', 'c', 1, 2],
 ['a', 'b', 1, 'c', 2],
 ['a', 1, 'b', 'c', 2],
 [1, 'a', 'b', 'c', 2]]

References:

[EilLan53]On the groups \(H(\pi, n)\), I, Samuel Eilenberg and Saunders Mac Lane, 1953.

Author:

  • Jean-Baptiste Priez
class sage.combinat.shuffle.SetShuffleProduct(l1, l2, element_constructor=None)

Bases: sage.structure.sage_object.SageObject

The union of all possible shuffle products of two sets of iterables.

EXAMPLES:

sage: from sage.combinat.shuffle import SetShuffleProduct
sage: sorted(SetShuffleProduct({(1,), (2,3)}, {(4,5), (6,)}))
[[1, 4, 5],
 [1, 6],
 [2, 3, 4, 5],
 [2, 3, 6],
 [2, 4, 3, 5],
 [2, 4, 5, 3],
 [2, 6, 3],
 [4, 1, 5],
 [4, 2, 3, 5],
 [4, 2, 5, 3],
 [4, 5, 1],
 [4, 5, 2, 3],
 [6, 1],
 [6, 2, 3]]
cardinality()

The cardinality is defined by the sum of the cardinality of all shuffles. That means by a sum of binomials.

class sage.combinat.shuffle.ShuffleProduct(l1, l2, element_constructor=None)

Bases: sage.structure.sage_object.SageObject

Shuffle product of two iterables.

EXAMPLES:

sage: from sage.combinat.shuffle import ShuffleProduct
sage: list(ShuffleProduct("abc", "de", element_constructor="".join))
['abcde',
 'adbce',
 'dabce',
 'abdce',
 'adebc',
 'daebc',
 'deabc',
 'adbec',
 'dabec',
 'abdec']
sage: list(ShuffleProduct("", "de", element_constructor="".join))
['de']
cardinality()

Return the number of shuffles of \(l_1\) and \(l_2\), respectively of lengths \(m\) and \(n\), which is \(\binom{m+n}{n}\).

class sage.combinat.shuffle.ShuffleProduct_overlapping(w1, w2, element_constructor=None, add=<built-in function add>)

Bases: sage.combinat.combinat.CombinatorialClass

The overlapping shuffle product of the two words w1 and w2.

If \(u\) and \(v\) are two words whose letters belong to an additive monoid or to another kind of alphabet on which addition is well-defined, then the overlapping shuffle product of \(u\) and \(v\) is a certain multiset of words defined as follows: Let \(a\) and \(b\) be the lengths of \(u\) and \(v\), respectively. Let \(A\) be the set \(\{(0, 1), (0, 2), \cdots, (0, a)\}\), and let \(B\) be the set \(\{(1, 1), (1, 2), \cdots, (1, b)\}\). Notice that the sets \(A\) and \(B\) are disjoint. We can make \(A\) and \(B\) into posets by setting \((k, i) \leq (k, j)\) for all \(k \in \{0, 1\}\) and \(i \leq j\). Then, \(A \cup B\) becomes a poset by disjoint union (we don’t set \((0, i) \leq (1, i)\)). Let \(p\) be the map from \(A \cup B\) to the set of all letters which sends every \((0, i)\) to the \(i\)-th letter of \(u\), and every \((1, j)\) to the \(j\)-th letter of \(v\). For every nonnegative integer \(c\) and every surjective map \(f : A \cup B \to \{ 1, 2, \cdots, c \}\) for which both restrictions \(f \mid_A\) and \(f \mid_B\) are strictly increasing, let \(w(f)\) be the length-\(c\) word such that for every \(1 \leq k \leq c\), the \(k\)-th letter of \(w(f)\) equals \(\sum_{j \in f^{-1}(k)} p(j)\) (this sum always has either one or two addends). The overlapping shuffle product of \(u\) and \(v\) is then the multiset of all \(w(f)\) with \(c\) ranging over all nonnegative integers and \(f\) ranging over the surjective maps \(f : A \cup B \to \{ 1, 2, \cdots, c \}\) for which both restrictions \(f \mid_A\) and \(f \mid_B\) are strictly increasing.

If one restricts \(c\) to a particular fixed nonnegative integer, then the multiset is instead called the overlapping shuffle product with precisely `a + b - c` overlaps. This is nonempty only if \(\max \{a, b\} \leq c \leq a + b\).

If \(c = a + b\), then the overlapping shuffle product with precisely \(a + b - c\) overlaps is plainly the shuffle product (ShuffleProduct_w1w2).

INPUT:

  • w1, w2 – iterables
  • element_constructor – (default: the parent of w1) the function used to construct the output
  • add – (default: +) the addition function

EXAMPLES:

sage: from sage.combinat.shuffle import ShuffleProduct_overlapping
sage: w, u = [[2, 9], [9, 1]]
sage: S = ShuffleProduct_overlapping(w, u)
sage: sorted(S)
[[2, 9, 1, 9],
 [2, 9, 9, 1],
 [2, 9, 9, 1],
 [2, 9, 10],
 [2, 18, 1],
 [9, 1, 2, 9],
 [9, 2, 1, 9],
 [9, 2, 9, 1],
 [9, 2, 10],
 [9, 3, 9],
 [11, 1, 9],
 [11, 9, 1],
 [11, 10]]
sage: A = [{1,2}, {3,4}]
sage: B = [{2,3}, {4,5,6}]
sage: S = ShuffleProduct_overlapping(A, B, add=lambda X,Y: X.union(Y))
sage: list(S)
[[{1, 2}, {3, 4}, {2, 3}, {4, 5, 6}],
 [{1, 2}, {2, 3}, {3, 4}, {4, 5, 6}],
 [{1, 2}, {2, 3}, {4, 5, 6}, {3, 4}],
 [{2, 3}, {1, 2}, {3, 4}, {4, 5, 6}],
 [{2, 3}, {1, 2}, {4, 5, 6}, {3, 4}],
 [{2, 3}, {4, 5, 6}, {1, 2}, {3, 4}],
 [{1, 2, 3}, {3, 4}, {4, 5, 6}],
 [{1, 2}, {2, 3, 4}, {4, 5, 6}],
 [{1, 2, 3}, {4, 5, 6}, {3, 4}],
 [{1, 2}, {2, 3}, {3, 4, 5, 6}],
 [{2, 3}, {1, 2, 4, 5, 6}, {3, 4}],
 [{2, 3}, {1, 2}, {3, 4, 5, 6}],
 [{1, 2, 3}, {3, 4, 5, 6}]]
class sage.combinat.shuffle.ShuffleProduct_overlapping_r(w1, w2, r, element_constructor=None, add=<built-in function add>)

Bases: sage.combinat.combinat.CombinatorialClass

The overlapping shuffle product of the two words w1 and w2 with precisely r overlaps.

See ShuffleProduct_overlapping for a definition.

EXAMPLES:

sage: from sage.combinat.shuffle import ShuffleProduct_overlapping_r
sage: w, u = map(Words(range(20)), [[2, 9], [9, 1]])
sage: S = ShuffleProduct_overlapping_r(w,u,1)
sage: list(S)
[word: 11,9,1,
 word: 2,18,1,
 word: 11,1,9,
 word: 2,9,10,
 word: 939,
 word: 9,2,10]