Shuffle product of iterables¶
The shuffle product of two sequences of lengths and
is a
sum over the
ways of interleaving the two sequences.
That could be defined inductively by:
with and
two non-empty sequences and if one of them is empty
then the product is equals to the other.
The shuffle product has been introduced by S. Eilenberg and S. Mac Lane in 1953 [EilLan53].
EXAMPLE:
sage: from sage.combinat.shuffle import ShuffleProduct
sage: list(ShuffleProduct([1,2], ["a", "b", "c"]))
[[1, 2, 'a', 'b', 'c'],
['a', 1, 2, 'b', 'c'],
[1, 'a', 2, 'b', 'c'],
['a', 'b', 1, 2, 'c'],
['a', 1, 'b', 2, 'c'],
[1, 'a', 'b', 2, 'c'],
['a', 'b', 'c', 1, 2],
['a', 'b', 1, 'c', 2],
['a', 1, 'b', 'c', 2],
[1, 'a', 'b', 'c', 2]]
References:
[EilLan53] | On the groups ![]() |
Author:
- Jean-Baptiste Priez
-
class
sage.combinat.shuffle.
SetShuffleProduct
(l1, l2, element_constructor=None)¶ Bases:
sage.structure.sage_object.SageObject
The union of all possible shuffle products of two sets of iterables.
TESTS:
sage: from sage.combinat.shuffle import SetShuffleProduct sage: TestSuite(SetShuffleProduct).run()
EXAMPLE:
sage: from sage.combinat.shuffle import SetShuffleProduct sage: sorted(SetShuffleProduct({(1,), (2,3)}, {(4,5), (6,)})) [[1, 4, 5], [1, 6], [2, 3, 4, 5], [2, 3, 6], [2, 4, 3, 5], [2, 4, 5, 3], [2, 6, 3], [4, 1, 5], [4, 2, 3, 5], [4, 2, 5, 3], [4, 5, 1], [4, 5, 2, 3], [6, 1], [6, 2, 3]]
-
cardinality
()¶ The cardinality is defined by the sum of the cardinality of all shuffles. That means by a sum of binomials.
TESTS:
sage: from sage.combinat.shuffle import SetShuffleProduct sage: SetShuffleProduct([[1,2],[3,4]], [[1,4]], element_constructor=set).cardinality() 12
-
-
class
sage.combinat.shuffle.
ShuffleProduct
(l1, l2, element_constructor=None)¶ Bases:
sage.structure.sage_object.SageObject
Shuffle product of two iterable.
EXAMPLES:
sage: from sage.combinat.shuffle import ShuffleProduct sage: list(ShuffleProduct("abc", "de", element_constructor="".join)) ['abcde', 'adbce', 'dabce', 'abdce', 'adebc', 'daebc', 'deabc', 'adbec', 'dabec', 'abdec'] sage: list(ShuffleProduct("", "de", element_constructor="".join)) ['de']
-
cardinality
()¶ Return the number of shuffles of
and
, respectively of lengths
and
, which is
.
TESTS:
sage: from sage.combinat.shuffle import ShuffleProduct sage: ShuffleProduct([3,1,2], [4,2,1,3]).cardinality() 35 sage: ShuffleProduct([3,1,2,5,6,4], [4,2,1,3]).cardinality() == binomial(10,4) True
-