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:
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.combinat.shuffle.ShuffleProduct_abstract
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.combinat.shuffle.ShuffleProduct_abstract
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_abstract(l1, l2, element_constructor=None)¶
Bases:
sage.structure.parent.Parent
Abstract base class for shuffle products.
- class sage.combinat.shuffle.ShuffleProduct_overlapping(w1, w2, element_constructor=None, add=<built-in function add>)¶
Bases:
sage.combinat.shuffle.ShuffleProduct_abstract
The overlapping shuffle product of the two words
w1
andw2
.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
– iterableselement_constructor
– (default: the parent ofw1
) the function used to construct the outputadd
– (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.shuffle.ShuffleProduct_abstract
The overlapping shuffle product of the two words
w1
andw2
with preciselyr
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]