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_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.structure.parent.Parent
,sage.structure.unique_representation.UniqueRepresentation
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(s) [word: 1234, word: 1324, word: 1342, word: 3124, word: 3142, word: 3412] sage: s == loads(dumps(s)) True sage: TestSuite(s).run() sage: s = ShuffleProduct_w1w2(W([1,4,3]),W([2])) sage: sorted(s) [word: 1243, word: 1423, word: 1432, word: 2143] sage: s = ShuffleProduct_w1w2(W([1,4,3]),W([])) sage: sorted(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