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)

Bases: sage.combinat.combination.Combinations_setk

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

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

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

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

sage: Combinations([1,2,3], 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]]

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

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

It is possible to take combinations of Sage objects:

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

class sage.combinat.combination.Combinations_mset(mset)

Bases: sage.structure.parent.Parent

cardinality()

class sage.combinat.combination.Combinations_msetk(mset, k)

Bases: sage.structure.parent.Parent

cardinality()

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()
12

class sage.combinat.combination.Combinations_set(mset)

Bases: sage.combinat.combination.Combinations_mset

cardinality()

Return the size of Combinations(set).

EXAMPLES:

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

rank(x)

EXAMPLES:

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

unrank(r)

EXAMPLES:

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

class sage.combinat.combination.Combinations_setk(mset, k)

Bases: sage.combinat.combination.Combinations_msetk

cardinality()

Return the size of combinations(set, k).

EXAMPLES:

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

list()

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

rank(x)

EXAMPLES:

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

unrank(r)

EXAMPLES:

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

sage.combinat.combination.from_rank(r, n, k)

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)

sage.combinat.combination.rank(comb, n, check=True)

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