# Shuffle product of words¶

The module sage.combinat.shuffle contains a more general implementation of shuffle product.

class sage.combinat.words.shuffle_product.ShuffleProduct_overlapping(w1, w2)

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

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)

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

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.

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)

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

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 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


#### Previous topic

Combinatorial classes of words.

#### Next topic

Suffix Tries and Suffix Trees