Shuffle product of words¶
See also
The module sage.combinat.shuffle
contains a more general
implementation of shuffle product.
-
class
sage.combinat.words.shuffle_product.
ShuffleProduct_overlapping
(w1, w2)¶ Bases:
sage.combinat.combinat.CombinatorialClass
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
).EXAMPLES:
sage: from sage.combinat.words.shuffle_product import ShuffleProduct_overlapping sage: w, u = map(Words(range(20)), [[2, 9], [9, 1]]) sage: S = ShuffleProduct_overlapping(w,u) sage: sorted([list(i) for i in list(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: S == loads(dumps(S)) True
-
class
sage.combinat.words.shuffle_product.
ShuffleProduct_overlapping_r
(w1, w2, r)¶ Bases:
sage.combinat.combinat.CombinatorialClass
The overlapping shuffle product of the two words
w1
andw2
with preciselyr
overlaps.See
ShuffleProduct_overlapping
for a definition.EXAMPLES:
sage: from sage.combinat.words.shuffle_product import ShuffleProduct_overlapping_r sage: w, u = map(Words(range(20)), [[2, 9], [9, 1]]) sage: S = ShuffleProduct_overlapping_r(w,u,1) sage: S == loads(dumps(S)) True
-
class
sage.combinat.words.shuffle_product.
ShuffleProduct_shifted
(w1, w2)¶ Bases:
sage.combinat.words.shuffle_product.ShuffleProduct_w1w2
Shifted shuffle product of
w1
withw2
.This is the shuffle product of
w1
with the word obtained by adding the length ofw1
to every letter ofw2
.Note that this class is meant to be used for words; it misbehaves when
w1
is a permutation or composition.EXAMPLES:
sage: from sage.combinat.words.shuffle_product import ShuffleProduct_shifted sage: w, u = Word([1,2]), Word([3,4]) sage: S = ShuffleProduct_shifted(w,u) sage: S == loads(dumps(S)) True
-
class
sage.combinat.words.shuffle_product.
ShuffleProduct_w1w2
(w1, w2)¶ Bases:
sage.combinat.combinat.CombinatorialClass
The shuffle product of the two words
w1
andw2
.If \(u\) and \(v\) are two words, then the 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. For every \(a\)-element subset \(I\) of \(\{1, 2, \cdots, a+b\}\), let \(w(I)\) be the length-\(a+b\) word such that:
- for every \(1 \leq k \leq a\), the \(i_k\)-th letter of \(w(I)\) is the \(k\)-th letter of \(u\), where \(i_k\) is the \(k\)-th smallest element of \(I\);
- for every \(1 \leq l \leq b\), the \(j_l\)-th letter of \(w(I)\) is the \(l\)-th letter of \(v\), where \(j_l\) is the \(l\)-th smallest element of \(\{1, 2, \cdots, a+b\} \setminus I\).
The shuffle product of \(u\) and \(v\) is then the multiset of all \(w(I)\) with \(I\) ranging over the \(a\)-element subsets of \(\{1, 2, \cdots, a+b\}\).
EXAMPLES:
sage: from sage.combinat.words.shuffle_product import ShuffleProduct_w1w2 sage: W = Words([1,2,3,4]) sage: s = ShuffleProduct_w1w2(W([1,2]),W([3,4])) sage: sorted(list(s)) [word: 1234, word: 1324, word: 1342, word: 3124, word: 3142, word: 3412] sage: s == loads(dumps(s)) True sage: s = ShuffleProduct_w1w2(W([1,4,3]),W([2])) sage: sorted(list(s)) [word: 1243, word: 1423, word: 1432, word: 2143] sage: s = ShuffleProduct_w1w2(W([1,4,3]),W([])) sage: sorted(list(s)) [word: 143]
-
cardinality
()¶ Return the number of words in the shuffle product of
w1
andw2
.This is understood as a multiset cardinality, not as a set cardinality; it does not count the distinct words only.
It is given by \(\binom{l_1+l_2}{l_1}\), where \(l_1\) is the length of
w1
and where \(l_2\) is the length ofw2
.EXAMPLES:
sage: from sage.combinat.words.shuffle_product import ShuffleProduct_w1w2 sage: w, u = map(Words("abcd"), ["ab", "cd"]) sage: S = ShuffleProduct_w1w2(w,u) sage: S.cardinality() 6 sage: w, u = map(Words("ab"), ["ab", "ab"]) sage: S = ShuffleProduct_w1w2(w,u) sage: S.cardinality() 6