comb

Documentation

Index

• func Coeff(n, k int) int
• func CoeffUint64(n, k uint64) uint64
• func Rank(comb []int) int
• func Unrank(rank, k int) []int
• type Iterator
  • func NewIterator(n, k int) *Iterator
  • func (b *Iterator) Next() bool
  • func (b Iterator) Value() []int
• type PartitionIterator
  • func NewPartitionIterator(n int) *PartitionIterator
  • func (pi *PartitionIterator) Next() bool
  • func (pi PartitionIterator) Value() [][]int

Functions

func Coeff

func Coeff(n, k int) int

Coeff calculates the binomial coefficient n choose k and returns it as an int. Coeff panics if the calculation would overflow.

func CoeffUint64

func CoeffUint64(n, k uint64) uint64

CoeffUint64 returns the binomial coefficient n choose k as a uint64. CoeffUint64 panics if the calculation would overflow the uint64.

func Rank

func Rank(comb []int) int

Rank converts a sorted set of distinct ints to an int such that the set of ints can be recovered by Unrank. Rank panics if calculating the rank would cause an overflow.

func Unrank

func Unrank(rank, k int) []int

Unrank converts an integer rank to a sorted set of k distinct ints. It is the inverse of rank.

Types

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

Iterator iterates over all ways of choosing k elements from 0, ..., n-1 in lexicographic order.

func NewIterator

func NewIterator(n, k int) *Iterator

NewIterator returns a new Iterator to iterate over all subsets of k distinct elements from 0, ..., n-1 in lexicographic order.

func (*Iterator) Next

func (b *Iterator) Next() bool

Next moves the Iterator to the next combination, returning true if there is one and false is there isn't.

func (Iterator) Value

func (b Iterator) Value() []int

Value returns the current state of the iterator. This must not be modified.

type PartitionIterator

type PartitionIterator struct {
	// contains filtered or unexported fields
}

PartitionIterator iterates over all partitions of the set {0, ..., n-1}. The partitions are generated in lexicographic order of their restricted growth strings. It is safe to modify the output of .Value().

func NewPartitionIterator

func NewPartitionIterator(n int) *PartitionIterator

TODO Handle n = 0 NewPartitionIterator returns a *PartitionIterator which iterates over all partitions of the set {0, ..., n-1}. The partitions are generated in lexicographic order of their restricted growth sequences.

func (*PartitionIterator) Next

func (pi *PartitionIterator) Next() bool

Next tries to advance pi to the next partition, returning true if there is one and false if there isn't.

func (PartitionIterator) Value

func (pi PartitionIterator) Value() [][]int

Value returns the current partition. It is safe to modify the output.