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, check=True)#

Bases: ShuffleProduct_w1w2

Shifted shuffle product of w1 with w2.

This is the shuffle product of w1 with the word obtained by adding the length of w1 to every letter of w2.

Note that this class is meant to be used for words; it misbehaves when w1 is a permutation or composition.

INPUT:

check – boolean (default True) whether to check that all words in the shuffle product belong to the correct parent

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, check=True)#

Bases: Parent, UniqueRepresentation

The shuffle product of the two words w1 and w2.

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\}\).

INPUT:

check – boolean (default True) whether to check that all words in the shuffle product belong to the correct parent

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 and w2.

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 of w2.

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