See also
The module sage.combinat.shuffle contains a more general implementation of shuffle product.
Bases: sage.combinat.combinat.CombinatorialClass
The overlapping shuffle product of the two words w1 and w2.
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
Bases: sage.combinat.combinat.CombinatorialClass
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
Bases: sage.combinat.words.shuffle_product.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.
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
Bases: sage.combinat.combinat.CombinatorialClass
The shuffle product of the two words w1 and w2.
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:
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]
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 , where
is the
length of w1 and where
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