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

Previous topic

Cartesian Products

Next topic

Substitutions over unit cube faces (Rauzy fractals)

This Page