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

TESTS:

sage: C = Combinations([1,2,3],2)
sage: C == loads(dumps(C))
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)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: C = Combinations(range(4))
sage: C == loads(dumps(C))
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)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: C = Combinations([1,2,3],2)
sage: C == loads(dumps(C))
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)

Bases: sage.combinat.combination.Combinations_mset

TESTS:

sage: C = Combinations(range(4))
sage: C == loads(dumps(C))
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)

Bases: sage.combinat.combination.Combinations_msetk

TESTS:

sage: C = Combinations([1,2,3],2)
sage: C == loads(dumps(C))
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