# Combinations¶

AUTHORS:

• Mike Hansen (2007): initial implementation
• Vincent Delecroix (2011): cleaning, bug corrections, doctests
class sage.combinat.combination.ChooseNK(mset, k)

TESTS:

sage: C = Combinations([1,2,3],2)
True

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


TESTS:

We check that the code works even for non mutable objects:

sage: l = [vector((0,0)), vector((0,1))]
sage: Combinations(l).list()
[[], [(0, 0)], [(0, 1)], [(0, 0), (0, 1)]]

class sage.combinat.combination.Combinations_mset(mset)

TESTS:

sage: C = Combinations(range(4))
True

cardinality()

TESTS:

sage: Combinations([1,2,3]).cardinality()
8
sage: Combinations(['a','a','b']).cardinality()
6

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

TESTS:

sage: C = Combinations([1,2,3],2)
True

cardinality()

Returns 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)

TESTS:

sage: C = Combinations(range(4))
True

rank(x)

EXAMPLES:

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

unrank(r)

EXAMPLES:

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

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

TESTS:

sage: C = Combinations([1,2,3],2)
True

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: range(c.cardinality()) == map(c.rank, c.list())
True

unrank(r)

EXAMPLES:

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


#### Previous topic

Fast computation of combinatorial functions (Cython + mpz).

#### Next topic

Combinatorial Algebras