Low-level Combinations

class sage.combinat.choose_nk.ChooseNK(n, k)

Bases: sage.combinat.combinat.CombinatorialClass

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'>

cardinality()

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

random_element()

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]

rank(x)

EXAMPLES:

sage: from sage.combinat.choose_nk import ChooseNK
sage: c52 = ChooseNK(5,2)
sage: range(c52.cardinality()) == map(c52.rank, c52)
True

unrank(r)

EXAMPLES:

sage: from sage.combinat.choose_nk import ChooseNK
sage: c52 = ChooseNK(5,2)
sage: c52.list() == map(c52.unrank, range(c52.cardinality()))
True

sage.combinat.choose_nk.from_rank(r, n, k)

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]

sage.combinat.choose_nk.rank(comb, n)

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