Combinations

AUTHORS:

  • Mike Hansen (2007): initial implementation
  • Vincent Delecroix (2011): cleaning, bug corrections, doctests
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.combinat.combinat.CombinatorialClass

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

Bases: sage.combinat.combinat.CombinatorialClass

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

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

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)

Returns 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 combinadics and James McCaffrey’s MSDN article. See: Wikipedia article Combinadic

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