Version: v0.9.1 Latest Latest Go to latest
Published: Mar 29, 2021 License: BSD-3-Clause

## Documentation ¶

### Overview ¶

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

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

#### func Binomial ¶

`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 ¶

`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 ¶

`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.

Example
```package main

import (
"fmt"

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

func main() {
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 ¶

`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 ¶

`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.

Example
```package main

import (
"fmt"

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

func main() {
// 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]
```
Example (Index)
```package main

import (
"fmt"

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

func main() {
// 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], data[c])
}

}
```
```Output:

ab
ac
ae
bc
bd
be
cd
ce
de
```

#### func GeneralizedBinomial ¶

`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 ¶

`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 ¶

`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.

Example
```package main

import (
"fmt"

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

func main() {
// 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 ¶

`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.

Example
```package main

import (
"fmt"

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

func main() {
// 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 ¶

`func LogGeneralizedBinomial(n, k float64) float64`

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

#### func NumPermutations ¶

`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 ¶

`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 ¶

`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.

Example
```package main

import (
"fmt"

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

func main() {
// 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]
```
Example (Index)
```package main

import (
"fmt"

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

func main() {
// 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], data[c])
}

}
```
```Output:

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

#### func SubFor ¶

`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.

### Types ¶

#### type CartesianGenerator ¶

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

CartesianGenerator iterates over a Cartesian product set.

Example
```package main

import (
"fmt"

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

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

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 ¶

`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 ¶

`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 ¶

`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 ¶

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

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

Example
```package main

import (
"fmt"

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

func main() {
// 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 ¶

`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 ¶

`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 ¶

`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 ¶

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

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

Example
```package main

import (
"fmt"

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

func main() {
// 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 ¶

`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 ¶

`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 ¶

`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.