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
. Ifk
is specified, then it returns the combinatorial class of combinations ofmset
of sizek
.A combination of a multiset
is an unordered selection of
objects of
, where every object can appear at most as many times as it appears in
.
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
-