Documentation

Overview

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

    Index

    Examples

    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
          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
              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)
              Output:
              
              ab
              ac
              ad
              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
                    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
                      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
                              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)
                              Output:
                              
                              ab
                              ba
                              ac
                              ca
                              ad
                              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
                                  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
                                          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
                                                  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.

                                                        Source Files