Low level combinatorial class of all possible choices of k elements out of range(n) without repetitions.
This is a low-level combinatorial class, with a simplistic interface by design. It aim at speed. It’s element are returned as plain list of python int.
EXAMPLES:
sage: from sage.combinat.choose_nk import ChooseNK
sage: c = ChooseNK(4,2)
sage: c.first()
[0, 1]
sage: c.list()
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
sage: type(c.list()[1])
<type 'list'>
sage: type(c.list()[1][1])
<type 'int'>
EXAMPLES:
sage: from sage.combinat.choose_nk import ChooseNK
sage: c52 = ChooseNK(5,2)
sage: [0,1] in c52
True
sage: [1,1] in c52
False
sage: [0,1,3] in c52
False
TESTS:
sage: from sage.combinat.choose_nk import ChooseNK
sage: c52 = ChooseNK(5,2)
sage: c52 == loads(dumps(c52))
True
An iterator for all choices of k things from range(n).
EXAMPLES:
sage: from sage.combinat.choose_nk import ChooseNK
sage: [c for c in ChooseNK(5,2)]
[[0, 1],
[0, 2],
[0, 3],
[0, 4],
[1, 2],
[1, 3],
[1, 4],
[2, 3],
[2, 4],
[3, 4]]
Returns the number of choices of k things from a list of n things.
EXAMPLES:
sage: from sage.combinat.choose_nk import ChooseNK
sage: ChooseNK(3,2).cardinality()
3
sage: ChooseNK(5,2).cardinality()
10
Returns a random choice of k things from range(n).
EXAMPLES:
sage: from sage.combinat.choose_nk import ChooseNK
sage: ChooseNK(5,2).random_element()
[0, 2]
EXAMPLES:
sage: from sage.combinat.choose_nk import ChooseNK
sage: c52 = ChooseNK(5,2)
sage: range(c52.cardinality()) == map(c52.rank, c52)
True
EXAMPLES:
sage: from sage.combinat.choose_nk import ChooseNK
sage: c52 = ChooseNK(5,2)
sage: c52.list() == map(c52.unrank, range(c52.cardinality()))
True
Returns the largest w < a such that binomial(w,b) <= x.
EXAMPLES:
sage: from sage.combinat.choose_nk import _comb_largest
sage: _comb_largest(6,3,10)
5
sage: _comb_largest(6,3,5)
4
Returns the combination of rank r in the subsets of range(n) of size k when listed in lexicographic order.
The algorithm used is based on combinadics and James McCaffrey’s MSDN article. See: http://en.wikipedia.org/wiki/Combinadic
EXAMPLES:
sage: import sage.combinat.choose_nk as choose_nk
sage: choose_nk.from_rank(0,3,0)
[]
sage: choose_nk.from_rank(0,3,1)
[0]
sage: choose_nk.from_rank(1,3,1)
[1]
sage: choose_nk.from_rank(2,3,1)
[2]
sage: choose_nk.from_rank(0,3,2)
[0, 1]
sage: choose_nk.from_rank(1,3,2)
[0, 2]
sage: choose_nk.from_rank(2,3,2)
[1, 2]
sage: choose_nk.from_rank(0,3,3)
[0, 1, 2]
Returns the rank of comb in the subsets of range(n) of size k.
The algorithm used is based on combinadics and James McCaffrey’s MSDN article. See: http://en.wikipedia.org/wiki/Combinadic
EXAMPLES:
sage: import sage.combinat.choose_nk as choose_nk
sage: choose_nk.rank([], 3)
0
sage: choose_nk.rank([0], 3)
0
sage: choose_nk.rank([1], 3)
1
sage: choose_nk.rank([2], 3)
2
sage: choose_nk.rank([0,1], 3)
0
sage: choose_nk.rank([0,2], 3)
1
sage: choose_nk.rank([1,2], 3)
2
sage: choose_nk.rank([0,1,2], 3)
0