gonum: gonum.org/v1/gonum/stat/combin Index | Examples | Files

package combin

import "gonum.org/v1/gonum/stat/combin"

Package combin implements routines involving combinatorics (permutations, combinations, etc.).

Index

Examples

Package Files

combin.go doc.go

func Binomial Uses

func Binomial(n, k int) int

Binomial returns the binomial coefficient of (n,k), also commonly referred to as "n choose k".

The binomial coefficient, C(n,k), is the number of unordered combinations of k elements in a set that is n elements big, and is defined as

C(n,k) = n!/((n-k)!k!)

n and k must be non-negative with n >= k, otherwise Binomial will panic. No check is made for overflow.

func Card Uses

func Card(dims []int) int

Card computes the cardinality of the multi-dimensional space whose dimensions have size specified by dims All length values must be positive, otherwise this will panic.

func Cartesian Uses

func Cartesian(lens []int) [][]int

Cartesian returns the Cartesian product of the slices in data. The Cartesian product of two sets is the set of all combinations of the items. For example, given the input

[]int{2, 3, 1}

the returned matrix will be

[ 0 0 0 ]
[ 0 1 0 ]
[ 0 2 0 ]
[ 1 0 0 ]
[ 1 1 0 ]
[ 1 2 0 ]

Cartesian panics if any of the provided lengths are less than 1.

Code:

fmt.Println("Generate Cartesian products for given lengths:")
lens := []int{1, 2, 3}
list := combin.Cartesian(lens)
for i, v := range list {
    fmt.Println(i, v)
}
// This is easy, but the number of combinations  can be very large,
// and generating all at once can use a lot of memory.
// For big data sets, consider using CartesianGenerator instead.

Output:

Generate Cartesian products for given lengths:
0 [0 0 0]
1 [0 0 1]
2 [0 0 2]
3 [0 1 0]
4 [0 1 1]
5 [0 1 2]

func CombinationIndex Uses

func CombinationIndex(comb []int, n, k int) int

CombinationIndex returns the index of the given combination.

The functions CombinationIndex and IndexToCombination define a bijection between the integers and the Binomial(n, k) number of possible combinations. CombinationIndex returns the inverse of IndexToCombination.

CombinationIndex panics if comb is not a sorted combination of the first [0,n) integers, if n or k are non-negative, or if k is greater than n.

func Combinations Uses

func Combinations(n, k int) [][]int

Combinations generates all of the combinations of k elements from a set of size n. The returned slice has length Binomial(n,k) and each inner slice has length k.

n and k must be non-negative with n >= k, otherwise Combinations will panic.

CombinationGenerator may alternatively be used to generate the combinations iteratively instead of collectively, or IndexToCombination for random access.

Code:

// combin provides several ways to work with the combinations of
// different objects. Combinations generates them directly.
fmt.Println("Generate list:")
n := 5
k := 3
list := combin.Combinations(n, k)
for i, v := range list {
    fmt.Println(i, v)
}
// This is easy, but the number of combinations  can be very large,
// and generating all at once can use a lot of memory.

Output:

Generate list:
0 [0 1 2]
1 [0 1 3]
2 [0 1 4]
3 [0 2 3]
4 [0 2 4]
5 [0 3 4]
6 [1 2 3]
7 [1 2 4]
8 [1 3 4]
9 [2 3 4]

Code:

// The integer slices returned from Combinations can be used to index
// into a data structure.
data := []string{"a", "b", "c", "d", "e"}
cs := combin.Combinations(len(data), 2)
for _, c := range cs {
    fmt.Printf("%s%s\n", data[c[0]], data[c[1]])
}

Output:

ab
ac
ad
ae
bc
bd
be
cd
ce
de

func GeneralizedBinomial Uses

func GeneralizedBinomial(n, k float64) float64

GeneralizedBinomial returns the generalized binomial coefficient of (n, k), defined as

Γ(n+1) / (Γ(k+1) Γ(n-k+1))

where Γ is the Gamma function. GeneralizedBinomial is useful for continuous relaxations of the binomial coefficient, or when the binomial coefficient value may overflow int. In the latter case, one may use math/big for an exact computation.

n and k must be non-negative with n >= k, otherwise GeneralizedBinomial will panic.

func IdxFor Uses

func IdxFor(sub, dims []int) int

IdxFor converts a multi-dimensional index into a linear index for a multi-dimensional space. sub specifies the index for each dimension, and dims specifies the size of each dimension. IdxFor is the inverse of SubFor. IdxFor panics if any of the entries of sub are negative, any of the entries of dim are non-positive, or if sub[i] >= dims[i] for any i.

func IndexToCombination Uses

func IndexToCombination(dst []int, idx, n, k int) []int

IndexToCombination returns the combination corresponding to the given index.

The functions CombinationIndex and IndexToCombination define a bijection between the integers and the Binomial(n, k) number of possible combinations. IndexToCombination returns the inverse of CombinationIndex (up to the order of the elements).

The combination is stored in-place into dst if dst is non-nil, otherwise a new slice is allocated and returned.

IndexToCombination panics if n or k are non-negative, if k is greater than n, or if idx is not in [0, Binomial(n,k)-1]. IndexToCombination will also panic if dst is non-nil and len(dst) is not k.

Code:

// combin provides several ways to work with the combinations of
// different objects. IndexToCombination allows random access into
// the combination order. Combined with CombinationIndex this
// provides a correspondence between integers and combinations.
n := 5
k := 3
comb := make([]int, k)
for i := 0; i < combin.Binomial(n, k); i++ {
    combin.IndexToCombination(comb, i, n, k) // can also use nil.
    idx := combin.CombinationIndex(comb, n, k)
    fmt.Println(i, comb, idx)
}

Output:

0 [0 1 2] 0
1 [0 1 3] 1
2 [0 1 4] 2
3 [0 2 3] 3
4 [0 2 4] 4
5 [0 3 4] 5
6 [1 2 3] 6
7 [1 2 4] 7
8 [1 3 4] 8
9 [2 3 4] 9

func IndexToPermutation Uses

func IndexToPermutation(dst []int, idx, n, k int) []int

IndexToPermutation returns the permutation corresponding to the given index.

The functions PermutationIndex and IndexToPermutation define a bijection between the integers and the NumPermutations(n, k) number of possible permutations. IndexToPermutation returns the inverse of PermutationIndex.

The permutation is stored in-place into dst if dst is non-nil, otherwise a new slice is allocated and returned.

IndexToPermutation panics if n or k are non-negative, if k is greater than n, or if idx is not in [0, NumPermutations(n,k)-1]. IndexToPermutation will also panic if dst is non-nil and len(dst) is not k.

Code:

// combin provides several ways to work with the permutations of
// different objects. IndexToPermutation allows random access into
// the permutation order. Combined with PermutationIndex this
// provides a correspondence between integers and permutations.
n := 4
k := 3
comb := make([]int, k)
for i := 0; i < combin.NumPermutations(n, k); i++ {
    combin.IndexToPermutation(comb, i, n, k) // can also use nil.
    idx := combin.PermutationIndex(comb, n, k)
    fmt.Println(i, comb, idx)
}

Output:

0 [0 1 2] 0
1 [0 2 1] 1
2 [1 0 2] 2
3 [1 2 0] 3
4 [2 0 1] 4
5 [2 1 0] 5
6 [0 1 3] 6
7 [0 3 1] 7
8 [1 0 3] 8
9 [1 3 0] 9
10 [3 0 1] 10
11 [3 1 0] 11
12 [0 2 3] 12
13 [0 3 2] 13
14 [2 0 3] 14
15 [2 3 0] 15
16 [3 0 2] 16
17 [3 2 0] 17
18 [1 2 3] 18
19 [1 3 2] 19
20 [2 1 3] 20
21 [2 3 1] 21
22 [3 1 2] 22
23 [3 2 1] 23

func LogGeneralizedBinomial Uses

func LogGeneralizedBinomial(n, k float64) float64

LogGeneralizedBinomial returns the log of the generalized binomial coefficient. See GeneralizedBinomial for more information.

func NumPermutations Uses

func NumPermutations(n, k int) int

NumPermutations returns the number of permutations when selecting k objects from a set of n objects when the selection order matters. No check is made for overflow.

NumPermutations panics if either n or k is negative, or if k is greater than n.

func PermutationIndex Uses

func PermutationIndex(perm []int, n, k int) int

PermutationIndex returns the index of the given permutation.

The functions PermutationIndex and IndexToPermutation define a bijection between the integers and the NumPermutations(n, k) number of possible permutations. PermutationIndex returns the inverse of IndexToPermutation.

PermutationIndex panics if perm is not a permutation of k of the first [0,n) integers, if n or k are non-negative, or if k is greater than n.

func Permutations Uses

func Permutations(n, k int) [][]int

Permutations generates all of the permutations of k elements from a set of size n. The returned slice has length NumPermutations(n, k) and each inner slice has length k.

n and k must be non-negative with n >= k, otherwise Permutations will panic.

PermutationGenerator may alternatively be used to generate the permutations iteratively instead of collectively, or IndexToPermutation for random access.

Code:

// combin provides several ways to work with the permutations of
// different objects. Permutations generates them directly.
fmt.Println("Generate list:")
n := 4
k := 3
list := combin.Permutations(n, k)
for i, v := range list {
    fmt.Println(i, v)
}
// This is easy, but the number of permutations can be very large,
// and generating all at once can use a lot of memory.

Output:

Generate list:
0 [0 1 2]
1 [0 2 1]
2 [1 0 2]
3 [1 2 0]
4 [2 0 1]
5 [2 1 0]
6 [0 1 3]
7 [0 3 1]
8 [1 0 3]
9 [1 3 0]
10 [3 0 1]
11 [3 1 0]
12 [0 2 3]
13 [0 3 2]
14 [2 0 3]
15 [2 3 0]
16 [3 0 2]
17 [3 2 0]
18 [1 2 3]
19 [1 3 2]
20 [2 1 3]
21 [2 3 1]
22 [3 1 2]
23 [3 2 1]

Code:

// The integer slices returned from Permutations can be used to index
// into a data structure.
data := []string{"a", "b", "c", "d"}
cs := combin.Permutations(len(data), 2)
for _, c := range cs {
    fmt.Printf("%s%s\n", data[c[0]], data[c[1]])
}

Output:

ab
ba
ac
ca
ad
da
bc
cb
bd
db
cd
dc

func SubFor Uses

func SubFor(sub []int, idx int, dims []int) []int

SubFor returns the multi-dimensional subscript for the input linear index to the multi-dimensional space. dims specifies the size of each dimension, and idx specifies the linear index. SubFor is the inverse of IdxFor.

If sub is non-nil the result is stored in-place into sub, and SubFor will panic if len(sub) != len(dims). If sub is nil a new slice of the appropriate length is allocated. SubFor panics if idx < 0 or if idx is greater than or equal to the product of the dimensions.

type CartesianGenerator Uses

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

CartesianGenerator iterates over a Cartesian product set.

Code:

fmt.Println("Generate products for given lengths:")
lens := []int{1, 2, 3}
gen := combin.NewCartesianGenerator(lens)

// Now loop over all products.
var i int
for gen.Next() {
    fmt.Println(i, gen.Product(nil))
    i++
}

Output:

Generate products for given lengths:
0 [0 0 0]
1 [0 0 1]
2 [0 0 2]
3 [0 1 0]
4 [0 1 1]
5 [0 1 2]

func NewCartesianGenerator Uses

func NewCartesianGenerator(lens []int) *CartesianGenerator

NewCartesianGenerator returns a CartesianGenerator for iterating over Cartesian products which are generated on the fly. All values in lens must be positive, otherwise this will panic.

func (*CartesianGenerator) Next Uses

func (g *CartesianGenerator) Next() bool

Next moves to the next product of the Cartesian set. It returns false if the generator reached the end of the Cartesian set end.

func (*CartesianGenerator) Product Uses

func (g *CartesianGenerator) Product(dst []int) []int

Product generates one product of the Cartesian set according to the current index which is increased by Next(). Next needs to be called at least one time before this method, otherwise it will panic.

type CombinationGenerator Uses

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

CombinationGenerator generates combinations iteratively. The Combinations function may be called to generate all combinations collectively.

Code:

// combin provides several ways to work with the combinations of
// different objects. CombinationGenerator constructs an iterator
// for the combinations.
n := 5
k := 3
gen := combin.NewCombinationGenerator(n, k)
idx := 0
for gen.Next() {
    fmt.Println(idx, gen.Combination(nil)) // can also store in-place.
    idx++
}

Output:

0 [0 1 2]
1 [0 1 3]
2 [0 1 4]
3 [0 2 3]
4 [0 2 4]
5 [0 3 4]
6 [1 2 3]
7 [1 2 4]
8 [1 3 4]
9 [2 3 4]

func NewCombinationGenerator Uses

func NewCombinationGenerator(n, k int) *CombinationGenerator

NewCombinationGenerator returns a CombinationGenerator for generating the combinations of k elements from a set of size n.

n and k must be non-negative with n >= k, otherwise NewCombinationGenerator will panic.

func (*CombinationGenerator) Combination Uses

func (c *CombinationGenerator) Combination(dst []int) []int

Combination returns the current combination. If dst is non-nil, it must have length k and the result will be stored in-place into dst. If dst is nil a new slice will be allocated and returned. If all of the combinations have already been constructed (Next() returns false), Combination will panic.

Next must be called to initialize the first value before calling Combination or Combination will panic. The value returned by Combination is only changed during calls to Next.

func (*CombinationGenerator) Next Uses

func (c *CombinationGenerator) Next() bool

Next advances the iterator if there are combinations remaining to be generated, and returns false if all combinations have been generated. Next must be called to initialize the first value before calling Combination or Combination will panic. The value returned by Combination is only changed during calls to Next.

type PermutationGenerator Uses

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

PermutationGenerator generates permutations iteratively. The Permutations function may be called to generate all permutations collectively.

Code:

// combin provides several ways to work with the permutations of
// different objects. PermutationGenerator constructs an iterator
// for the permutations.
n := 4
k := 3
gen := combin.NewPermutationGenerator(n, k)
idx := 0
for gen.Next() {
    fmt.Println(idx, gen.Permutation(nil)) // can also store in-place.
    idx++
}

Output:

0 [0 1 2]
1 [0 2 1]
2 [1 0 2]
3 [1 2 0]
4 [2 0 1]
5 [2 1 0]
6 [0 1 3]
7 [0 3 1]
8 [1 0 3]
9 [1 3 0]
10 [3 0 1]
11 [3 1 0]
12 [0 2 3]
13 [0 3 2]
14 [2 0 3]
15 [2 3 0]
16 [3 0 2]
17 [3 2 0]
18 [1 2 3]
19 [1 3 2]
20 [2 1 3]
21 [2 3 1]
22 [3 1 2]
23 [3 2 1]

func NewPermutationGenerator Uses

func NewPermutationGenerator(n, k int) *PermutationGenerator

NewPermutationGenerator returns a PermutationGenerator for generating the permutations of k elements from a set of size n.

n and k must be non-negative with n >= k, otherwise NewPermutationGenerator will panic.

func (*PermutationGenerator) Next Uses

func (p *PermutationGenerator) Next() bool

Next advances the iterator if there are permutations remaining to be generated, and returns false if all permutations have been generated. Next must be called to initialize the first value before calling Permutation or Permutation will panic. The value returned by Permutation is only changed during calls to Next.

func (*PermutationGenerator) Permutation Uses

func (p *PermutationGenerator) Permutation(dst []int) []int

Permutation returns the current permutation. If dst is non-nil, it must have length k and the result will be stored in-place into dst. If dst is nil a new slice will be allocated and returned. If all of the permutations have already been constructed (Next() returns false), Permutation will panic.

Next must be called to initialize the first value before calling Permutation or Permutation will panic. The value returned by Permutation is only changed during calls to Next.

Package combin imports 2 packages (graph) and is imported by 5 packages. Updated 2019-12-02. Refresh now. Tools for package owners.