Combinations

AUTHORS:

  • Mike Hansen (2007): initial implementation

  • Vincent Delecroix (2011): cleaning, bug corrections, doctests

  • Antoine Genitrini (2020) : new implementation of the lexicographic unranking of combinations

class sage.combinat.combination.ChooseNK(mset, k)[source]

Bases: Combinations_setk

sage.combinat.combination.Combinations(mset, k=None)[source]

Return the combinatorial class of combinations of the multiset mset. If k is specified, then it returns the combinatorial class of combinations of mset of size k.

A combination of a multiset \(M\) is an unordered selection of \(k\) objects of \(M\), where every object can appear at most as many times as it appears in \(M\).

The combinatorial classes correctly handle the cases where mset has duplicate elements.

EXAMPLES:

sage: C = Combinations(range(4)); C
Combinations of [0, 1, 2, 3]
sage: C.list()
[[],
 [0],
 [1],
 [2],
 [3],
 [0, 1],
 [0, 2],
 [0, 3],
 [1, 2],
 [1, 3],
 [2, 3],
 [0, 1, 2],
 [0, 1, 3],
 [0, 2, 3],
 [1, 2, 3],
 [0, 1, 2, 3]]
 sage: C.cardinality()
 16

>>> from sage.all import *
>>> C = Combinations(range(Integer(4))); C
Combinations of [0, 1, 2, 3]
>>> C.list()
[[],
 [0],
 [1],
 [2],
 [3],
 [0, 1],
 [0, 2],
 [0, 3],
 [1, 2],
 [1, 3],
 [2, 3],
 [0, 1, 2],
 [0, 1, 3],
 [0, 2, 3],
 [1, 2, 3],
 [0, 1, 2, 3]]
>>> C.cardinality()
 16


sage: C2 = Combinations(range(4),2); C2
Combinations of [0, 1, 2, 3] of length 2
sage: C2.list()
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
sage: C2.cardinality()
6

>>> from sage.all import *
>>> C2 = Combinations(range(Integer(4)),Integer(2)); C2
Combinations of [0, 1, 2, 3] of length 2
>>> C2.list()
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
>>> C2.cardinality()
6


sage: Combinations([1,2,2,3]).list()
[[],
 [1],
 [2],
 [3],
 [1, 2],
 [1, 3],
 [2, 2],
 [2, 3],
 [1, 2, 2],
 [1, 2, 3],
 [2, 2, 3],
 [1, 2, 2, 3]]

>>> from sage.all import *
>>> Combinations([Integer(1),Integer(2),Integer(2),Integer(3)]).list()
[[],
 [1],
 [2],
 [3],
 [1, 2],
 [1, 3],
 [2, 2],
 [2, 3],
 [1, 2, 2],
 [1, 2, 3],
 [2, 2, 3],
 [1, 2, 2, 3]]


sage: Combinations([1,2,3], 2).list()
[[1, 2], [1, 3], [2, 3]]

>>> from sage.all import *
>>> Combinations([Integer(1),Integer(2),Integer(3)], Integer(2)).list()
[[1, 2], [1, 3], [2, 3]]


sage: mset = [1,1,2,3,4,4,5]
sage: Combinations(mset,2).list()
[[1, 1],
 [1, 2],
 [1, 3],
 [1, 4],
 [1, 5],
 [2, 3],
 [2, 4],
 [2, 5],
 [3, 4],
 [3, 5],
 [4, 4],
 [4, 5]]

>>> from sage.all import *
>>> mset = [Integer(1),Integer(1),Integer(2),Integer(3),Integer(4),Integer(4),Integer(5)]
>>> Combinations(mset,Integer(2)).list()
[[1, 1],
 [1, 2],
 [1, 3],
 [1, 4],
 [1, 5],
 [2, 3],
 [2, 4],
 [2, 5],
 [3, 4],
 [3, 5],
 [4, 4],
 [4, 5]]


sage: mset = ["d","a","v","i","d"]
sage: Combinations(mset,3).list()
[['d', 'd', 'a'],
 ['d', 'd', 'v'],
 ['d', 'd', 'i'],
 ['d', 'a', 'v'],
 ['d', 'a', 'i'],
 ['d', 'v', 'i'],
 ['a', 'v', 'i']]

>>> from sage.all import *
>>> mset = ["d","a","v","i","d"]
>>> Combinations(mset,Integer(3)).list()
[['d', 'd', 'a'],
 ['d', 'd', 'v'],
 ['d', 'd', 'i'],
 ['d', 'a', 'v'],
 ['d', 'a', 'i'],
 ['d', 'v', 'i'],
 ['a', 'v', 'i']]


sage: X = Combinations([1,2,3,4,5],3)
sage: [x for x in X]
[[1, 2, 3],
 [1, 2, 4],
 [1, 2, 5],
 [1, 3, 4],
 [1, 3, 5],
 [1, 4, 5],
 [2, 3, 4],
 [2, 3, 5],
 [2, 4, 5],
 [3, 4, 5]]

>>> from sage.all import *
>>> X = Combinations([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)],Integer(3))
>>> [x for x in X]
[[1, 2, 3],
 [1, 2, 4],
 [1, 2, 5],
 [1, 3, 4],
 [1, 3, 5],
 [1, 4, 5],
 [2, 3, 4],
 [2, 3, 5],
 [2, 4, 5],
 [3, 4, 5]]

It is possible to take combinations of Sage objects:

sage: Combinations([vector([1,1]), vector([2,2]), vector([3,3])], 2).list()     # needs sage.modules
[[(1, 1), (2, 2)], [(1, 1), (3, 3)], [(2, 2), (3, 3)]]

>>> from sage.all import *
>>> Combinations([vector([Integer(1),Integer(1)]), vector([Integer(2),Integer(2)]), vector([Integer(3),Integer(3)])], Integer(2)).list()     # needs sage.modules
[[(1, 1), (2, 2)], [(1, 1), (3, 3)], [(2, 2), (3, 3)]]
class sage.combinat.combination.Combinations_mset(mset)[source]

Bases: Parent

cardinality()[source]
class sage.combinat.combination.Combinations_msetk(mset, k)[source]

Bases: Parent

cardinality()[source]

Return the size of combinations(mset, k).

IMPLEMENTATION: Wraps GAP’s NrCombinations.

EXAMPLES:

sage: mset = [1,1,2,3,4,4,5]
sage: Combinations(mset,2).cardinality()                                    # needs sage.libs.gap
12

>>> from sage.all import *
>>> mset = [Integer(1),Integer(1),Integer(2),Integer(3),Integer(4),Integer(4),Integer(5)]
>>> Combinations(mset,Integer(2)).cardinality()                                    # needs sage.libs.gap
12
class sage.combinat.combination.Combinations_set(mset)[source]

Bases: Combinations_mset

cardinality()[source]

Return the size of Combinations(set).

EXAMPLES:

sage: Combinations(range(16000)).cardinality() == 2^16000
True

>>> from sage.all import *
>>> Combinations(range(Integer(16000))).cardinality() == Integer(2)**Integer(16000)
True
rank(x)[source]

EXAMPLES:

sage: c = Combinations([1,2,3])
sage: list(range(c.cardinality())) == list(map(c.rank, c))
True

>>> from sage.all import *
>>> c = Combinations([Integer(1),Integer(2),Integer(3)])
>>> list(range(c.cardinality())) == list(map(c.rank, c))
True
unrank(r)[source]

EXAMPLES:

sage: c = Combinations([1,2,3])
sage: c.list() == list(map(c.unrank, range(c.cardinality())))
True

>>> from sage.all import *
>>> c = Combinations([Integer(1),Integer(2),Integer(3)])
>>> c.list() == list(map(c.unrank, range(c.cardinality())))
True
class sage.combinat.combination.Combinations_setk(mset, k)[source]

Bases: Combinations_msetk

cardinality()[source]

Return the size of combinations(set, k).

EXAMPLES:

sage: Combinations(range(16000), 5).cardinality()
8732673194560003200

>>> from sage.all import *
>>> Combinations(range(Integer(16000)), Integer(5)).cardinality()
8732673194560003200
list()[source]

EXAMPLES:

sage: Combinations([1,2,3,4,5],3).list()
[[1, 2, 3],
 [1, 2, 4],
 [1, 2, 5],
 [1, 3, 4],
 [1, 3, 5],
 [1, 4, 5],
 [2, 3, 4],
 [2, 3, 5],
 [2, 4, 5],
 [3, 4, 5]]

>>> from sage.all import *
>>> Combinations([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)],Integer(3)).list()
[[1, 2, 3],
 [1, 2, 4],
 [1, 2, 5],
 [1, 3, 4],
 [1, 3, 5],
 [1, 4, 5],
 [2, 3, 4],
 [2, 3, 5],
 [2, 4, 5],
 [3, 4, 5]]
rank(x)[source]

EXAMPLES:

sage: c = Combinations([1,2,3], 2)
sage: list(range(c.cardinality())) == list(map(c.rank, c.list()))
True

>>> from sage.all import *
>>> c = Combinations([Integer(1),Integer(2),Integer(3)], Integer(2))
>>> list(range(c.cardinality())) == list(map(c.rank, c.list()))
True
unrank(r)[source]

EXAMPLES:

sage: c = Combinations([1,2,3], 2)
sage: c.list() == list(map(c.unrank, range(c.cardinality())))
True

>>> from sage.all import *
>>> c = Combinations([Integer(1),Integer(2),Integer(3)], Integer(2))
>>> c.list() == list(map(c.unrank, range(c.cardinality())))
True
sage.combinat.combination.from_rank(r, n, k)[source]

Return the combination of rank r in the subsets of range(n) of size k when listed in lexicographic order.

The algorithm used is based on factoradics and presented in [DGH2020]. It is there compared to the other from the literature.

EXAMPLES:

sage: import sage.combinat.combination as combination
sage: combination.from_rank(0,3,0)
()
sage: combination.from_rank(0,3,1)
(0,)
sage: combination.from_rank(1,3,1)
(1,)
sage: combination.from_rank(2,3,1)
(2,)
sage: combination.from_rank(0,3,2)
(0, 1)
sage: combination.from_rank(1,3,2)
(0, 2)
sage: combination.from_rank(2,3,2)
(1, 2)
sage: combination.from_rank(0,3,3)
(0, 1, 2)

>>> from sage.all import *
>>> import sage.combinat.combination as combination
>>> combination.from_rank(Integer(0),Integer(3),Integer(0))
()
>>> combination.from_rank(Integer(0),Integer(3),Integer(1))
(0,)
>>> combination.from_rank(Integer(1),Integer(3),Integer(1))
(1,)
>>> combination.from_rank(Integer(2),Integer(3),Integer(1))
(2,)
>>> combination.from_rank(Integer(0),Integer(3),Integer(2))
(0, 1)
>>> combination.from_rank(Integer(1),Integer(3),Integer(2))
(0, 2)
>>> combination.from_rank(Integer(2),Integer(3),Integer(2))
(1, 2)
>>> combination.from_rank(Integer(0),Integer(3),Integer(3))
(0, 1, 2)
sage.combinat.combination.rank(comb, n, check=True)[source]

Return the rank of comb in the subsets of range(n) of size k where k is the length of comb.

The algorithm used is based on combinadics and James McCaffrey’s MSDN article. See: Wikipedia article Combinadic.

EXAMPLES:

sage: import sage.combinat.combination as combination
sage: combination.rank((), 3)
0
sage: combination.rank((0,), 3)
0
sage: combination.rank((1,), 3)
1
sage: combination.rank((2,), 3)
2
sage: combination.rank((0,1), 3)
0
sage: combination.rank((0,2), 3)
1
sage: combination.rank((1,2), 3)
2
sage: combination.rank((0,1,2), 3)
0

sage: combination.rank((0,1,2,3), 3)
Traceback (most recent call last):
...
ValueError: len(comb) must be <= n
sage: combination.rank((0,0), 2)
Traceback (most recent call last):
...
ValueError: comb must be a subword of (0,1,...,n)

sage: combination.rank([1,2], 3)
2
sage: combination.rank([0,1,2], 3)
0

>>> from sage.all import *
>>> import sage.combinat.combination as combination
>>> combination.rank((), Integer(3))
0
>>> combination.rank((Integer(0),), Integer(3))
0
>>> combination.rank((Integer(1),), Integer(3))
1
>>> combination.rank((Integer(2),), Integer(3))
2
>>> combination.rank((Integer(0),Integer(1)), Integer(3))
0
>>> combination.rank((Integer(0),Integer(2)), Integer(3))
1
>>> combination.rank((Integer(1),Integer(2)), Integer(3))
2
>>> combination.rank((Integer(0),Integer(1),Integer(2)), Integer(3))
0

>>> combination.rank((Integer(0),Integer(1),Integer(2),Integer(3)), Integer(3))
Traceback (most recent call last):
...
ValueError: len(comb) must be <= n
>>> combination.rank((Integer(0),Integer(0)), Integer(2))
Traceback (most recent call last):
...
ValueError: comb must be a subword of (0,1,...,n)

>>> combination.rank([Integer(1),Integer(2)], Integer(3))
2
>>> combination.rank([Integer(0),Integer(1),Integer(2)], Integer(3))
0