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 \(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
-
-
sage.combinat.combination.
from_rank
(r, n, k)¶ Returns the combination of rank
r
in the subsets ofrange(n)
of sizek
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 ofrange(n)
of sizek
wherek
is the length ofcomb
.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