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
and
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
and
is a certain multiset of words defined as follows: Let
and
be the lengths of
and
, respectively. Let
be the set
, and let
be the set
. Notice that the sets
and
are disjoint. We can make
and
into posets by setting
for all
and
. Then,
becomes a poset by disjoint union (we don’t set
). Let
be the map from
to the set of all letters which sends every
to the
-th letter of
, and every
to the
-th letter of
. For every nonnegative integer
and every surjective map
for which both restrictions
and
are strictly increasing, let
be the length-
word such that for every
, the
-th letter of
equals
(this sum always has either one or two addends). The overlapping shuffle product of
and
is then the multiset of all
with
ranging over all nonnegative integers and
ranging over the surjective maps
for which both restrictions
and
are strictly increasing.
If one restricts
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
.
If
, then the overlapping shuffle product with precisely
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
and
are two words, then the shuffle product of
and
is a certain multiset of words defined as follows: Let
and
be the lengths of
and
, respectively. For every
-element subset
of
, let
be the length-
word such that:
- for every
, the
-th letter of
is the
-th letter of
, where
is the
-th smallest element of
;
- for every
, the
-th letter of
is the
-th letter of
, where
is the
-th smallest element of
.
The shuffle product of
and
is then the multiset of all
with
ranging over the
-element subsets of
.
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
, where
is the length of
w1
and whereis 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
- for every