kombinat

package module
v0.0.0-...-2c1092c Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 19, 2024 License: MIT Imports: 2 Imported by: 0

README

Kombinat

Go Reference

Package kombinat implements generic combinatorics functions and generators for producing combinations, permutations, multiset permutations and variations from elements in a slice of any type in Go language.

The goal of this library is the ability to efficiently permute elements of a slice for different testing and probing scenarios. If you need a mathematics library that also has many more features, use Gonum instead.

The package consists of the following functions and generators:

  • Combinations via Chase's Twiddle algorithm, based on this implementation in C
  • Permutations without repetition by using non-recursive Heap's algorithm
  • Multiset permutations (permutations with repetition) based on Algorithm 1 found in "Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts." by Aaron Williams, 2009
  • Variations (custom)

Generators are generaly recommended as they are not only faster, but also memory efficient, and can store results into different slices. If you need to reuse the results many times, functions that generate the entire result set are also available.

Production

The package is heavily used in a simple web game My Number (Moj Broj) that is similar in spirit to Countdown Numbers, but modeled after one of the games in the popular TV show Slagalica on Radio Television of Serbia.

Usage

Generators

Initialization

To create & initialize, for example, a CombinationGenerator, you can use the following code:

items := []string{"A", "B", "C"}

gen, err := NewCombinationGenerator(2, items)
// or
gen2 := new(CombinationGenerator[string])
err2 := gen2.Init(2, items)

Generator instance can be reused by invoking Init with different input arguments of the same type. Previous data will be overwritten.

Iteration

To have the generator produce another result, call the Next method. The method returns true until it reaches the end of the sequence, and therefore can be used in a for loop.

To access the new result, call Current or CurrentCopy after calling Next (it has to be called at least once!). Current will return the internaly used slice, whereas CurrentCopy will return a copy of the internal slice. Use the former if you are not going to modify the slice in order to avoid allocation. But if modification of the slice is expected, use CurrentCopy in order not to interfere with the generator and cause unexpected behavior.

For example:

for gen.Next() {
  fmt.Printf("%v\n", gen.Current())
  list = append(list, gen.CurrentCopy())
}

It is possible to set a slice that will be updated whenever Next is called by using SetDest method. This also enables partial updates of a larger slice, for example:

items := []string{"A", "B", "C"}
dest := []string{"i", "j", "k", "l"}

gen, err := NewCombinationGenerator(2, items)
gen.SetDest(dest[1:3])

gen.Next()
fmt.Printf("%v", dest) // [i, B, C, l]

After a new destination slice is set, subsequent calls to Current will always return the slice that was set, making the call redundant.

To make the generator start from the beginning, call Reset. Reset preserves the destination slice.

Functions

Function call returns a slice of slices, containing the entire result set. For example:

ps, err := Permutations([]int{1, 2, 3, 4, 5}) //[][]int

Warning: be careful when using these functions, as they could use up a lot of memory for larger values.

Benchmarks

Some benchmarks run on Apple M1 Pro can be found below:

goos: darwin
goarch: arm64
pkg: github.com/drazengolic/kombinat

Combinations

go test -bench BenchmarkCombinations -benchmem -benchtime=10s

BenchmarkCombinations/c(2,6)=15-8           26261770         442.7 ns/op       704 B/op       18 allocs/op
BenchmarkCombinations/c(3,6)=20-8           20279744         591.3 ns/op      1048 B/op       23 allocs/op
BenchmarkCombinations/c(4,6)=15-8           25988402         459.6 ns/op       960 B/op       18 allocs/op
BenchmarkCombinations/c(5,6)=6-8            53533160         222.0 ns/op       544 B/op        9 allocs/op
BenchmarkCombinations/c(6,6)=1-8            123885088         96.82 ns/op      184 B/op        4 allocs/op

go test -bench BenchmarkCombinationGenerator -benchmem -benchtime=10s

BenchmarkCombinationGenerator/c(2,6)=15-8           81718262         126.7 ns/op        80 B/op        2 allocs/op
BenchmarkCombinationGenerator/c(3,6)=20-8           75011426         157.6 ns/op        88 B/op        2 allocs/op
BenchmarkCombinationGenerator/c(4,6)=15-8           93862041         126.8 ns/op        96 B/op        2 allocs/op
BenchmarkCombinationGenerator/c(5,6)=6-8            151733102         78.96 ns/op      112 B/op        2 allocs/op
BenchmarkCombinationGenerator/c(6,6)=1-8            224967640         53.35 ns/op      112 B/op        2 allocs/op

Permutations

go test -bench BenchmarkPermutations -benchmem -benchtime=10s

BenchmarkPermutations/p(2)=2-8          133187949         90.06 ns/op      112 B/op        5 allocs/op
BenchmarkPermutations/p(3)=6-8          56977621         208.8 ns/op       336 B/op        9 allocs/op
BenchmarkPermutations/p(4)=24-8         18749431         637.7 ns/op      1408 B/op       27 allocs/op
BenchmarkPermutations/p(5)=120-8         4090677        2933 ns/op        8928 B/op      123 allocs/op
BenchmarkPermutations/p(6)=720-8          668253       17674 ns/op       53088 B/op      723 allocs/op

go test -bench BenchmarkPermutationGenerator -benchmem -benchtime=10s

BenchmarkPermutationGenerator/p(2)=2-8          310151914         38.68 ns/op       32 B/op        2 allocs/op
BenchmarkPermutationGenerator/p(3)=6-8          218699462         54.79 ns/op       48 B/op        2 allocs/op
BenchmarkPermutationGenerator/p(4)=24-8         92384619         128.1 ns/op        64 B/op        2 allocs/op
BenchmarkPermutationGenerator/p(5)=120-8        24015909         499.2 ns/op        96 B/op        2 allocs/op
BenchmarkPermutationGenerator/p(6)=720-8         4256427        2819 ns/op          96 B/op        2 allocs/op

MultiPermutations

go test -bench BenchmarkMultiPermutations -benchmem -benchtime=10s

BenchmarkMultiPermutations/P(AABCCCDD)-8            123399       97058 ns/op      342145 B/op     1700 allocs/op
BenchmarkMultiPermutations/P(AABB)-8              28815830         414.8 ns/op       832 B/op       14 allocs/op
BenchmarkMultiPermutations/P(ABCD)-8               9078172        1314 ns/op        3136 B/op       34 allocs/op

go test -bench BenchmarkMultiPermutationGenerator -benchmem -benchtime=10s

BenchmarkMultiPermutationGenerator/P(AABCCCDD)-8            447722       24886 ns/op         192 B/op        9 allocs/op
BenchmarkMultiPermutationGenerator/P(AABB)-8              76625335         154.6 ns/op        96 B/op        5 allocs/op
BenchmarkMultiPermutationGenerator/P(ABCD)-8              34821980         343.3 ns/op        96 B/op        5 allocs/op

Variations

go test -bench BenchmarkVariations -benchmem -benchtime=10s

BenchmarkVariations/v(2,4)=16-8           38591599         296.7 ns/op       656 B/op       18 allocs/op
BenchmarkVariations/v(3,4)=64-8            9806036        1217 ns/op        3096 B/op       66 allocs/op
BenchmarkVariations/v(4,4)=256-8           2516913        4775 ns/op       14368 B/op      258 allocs/op
BenchmarkVariations/v(5,4)=1024-8           577398       20656 ns/op       73776 B/op     1026 allocs/op
BenchmarkVariations/v(6,4)=4096-8           141417       85309 ns/op      294960 B/op     4098 allocs/op

go test -bench BenchmarkVariationGenerator -benchmem -benchtime=10s

BenchmarkVariationGenerator/v(2,4)=16-8           227415219         52.79 ns/op        0 B/op        0 allocs/op
BenchmarkVariationGenerator/v(3,4)=64-8           36819321         325.0 ns/op         0 B/op        0 allocs/op
BenchmarkVariationGenerator/v(4,4)=256-8           8336451        1438 ns/op           0 B/op        0 allocs/op
BenchmarkVariationGenerator/v(5,4)=1024-8          1733893        6920 ns/op           0 B/op        0 allocs/op
BenchmarkVariationGenerator/v(6,4)=4096-8           367791       32557 ns/op           0 B/op        0 allocs/op

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Binom 

func Binom(k, n int) int

Binom calculates the binomial coefficient.

func CombinationCount 

func CombinationCount(m, n int) int

func Combinations 

func Combinations[T any](m int, elems []T) ([][]T, error)

Combinations by the Chase's Twiddle algorithm (1970), based on implementation in C by Matthew Belmonte in 1996.

Returns error if the input slice is empty or nil, or if m is less than 1 or bigger than len(elems).

func Fac 

func Fac(n int) int

Fac calculates factorial of n (n!)

func IntPow 

func IntPow(n, m int) int

IntPow calculates n^m as integer

func MultiPermutations 

func MultiPermutations[T any](elems []T, reps []int) ([][]T, error)

This function generates permutations of a multiset by following the algorithm described below. It accepts slices

  • elems: set of elements to make permutations from
  • reps: number of repetitions per element, must be 1 or higher.

Number of items in both slices must match, as reps correspond to the elems.

Algorithm 1 Visits the permutations of multiset E. The permutations are stored in a singly-linked list pointed to by head pointer h. Each node in the linked list has a value field v and a next field n. The init(E) call creates a singly-linked list storing the elements of E in non-increasing order with h, i, and j pointing to its first, second-last, and last nodes, respectively. The null pointer is given by φ. Note: If E is empty, then init(E) should exit. Also, if E contains only one element, then init(E) does not need to provide a value for i. 

[h, i, j] ← init(E)
visit(h)
while j.n ≠ φ orj.v < h.v do
	if j.n ≠ φ and i.v ≥ j.n.v then
    	s←j
	else
    	s←i
	end if
	t ← s.n
	s.n ← t.n
	t.n ← h
	if t.v < h.v then
    	i←t
	end if
	j←i.n
	h←t
	visit(h)
end while

Found in "Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts." Aaron Williams, 2009

For implementations in other languages, check out multipermute.

func MultiPermutationsCount 

func MultiPermutationsCount(reps []int) int

func PermutationCount 

func PermutationCount(n int) int

func Permutations 

func Permutations[T any](elems []T) ([][]T, error)

Permutations without repetition by using non-recursive Heap's algorithm. Returns an error if elems is empty or nil.

func VariationCount 

func VariationCount(k, n int) int

func Variations 

func Variations[T any](k int, elems []T) ([][]T, error)

Variations with repetitions. Returns an error when k <= 0 or when elems is nil or empty.

Types

type CombinationGenerator 

type CombinationGenerator[T any] struct {
	// contains filtered or unexported fields
}

CombinationGenerator implements a Generator interface for generating combinations of size m out of elements in elems slice on every invocation of the CombinationGenerator.Next method. For algorithm details see Combinations.

func NewCombinationGenerator 

func NewCombinationGenerator[T any](m int, elems []T) (*CombinationGenerator[T], error)

NewCombinationGenerator creates and initializes a new CombinationGenerator. Arguments and returned errors are the same ones from the CombinationGenerator.Init method.

func (*CombinationGenerator[T]) Current 

func (gen *CombinationGenerator[T]) Current() []T

Current returns the internal slice that holds the current combination. If you need to modify the returned slice, use CombinationGenerator.CurrentCopy instead.

func (*CombinationGenerator[T]) CurrentCopy 

func (gen *CombinationGenerator[T]) CurrentCopy() []T

CurrentCopy returns a copy of the internal slice that holds the current combination. If you don't need to modify the returned slice, use CombinationGenerator.Current to avoid allocation.

func (*CombinationGenerator[T]) Init 

func (gen *CombinationGenerator[T]) Init(m int, elems []T) error

Init initializes a generator of combinations of size m out of elements in the elems slice.

func (*CombinationGenerator[T]) Next 

func (gen *CombinationGenerator[T]) Next() bool

Next produces a new combination in the generator. If it returns false, there are no more combinations available.

func (*CombinationGenerator[T]) Reset 

func (gen *CombinationGenerator[T]) Reset()

Reset resets the generator to the beginning of the sequence.

func (*CombinationGenerator[T]) SetDest 

func (gen *CombinationGenerator[T]) SetDest(dest []T) error

SetDest sets a destination slice that will receive the results. Returns an error if there's not enough capacity in the slice.

After the destination slice is set, subsequent calls to CombinationGenerator.Current will return the provided slice.

type Generator 

type Generator[T any] interface {
	Current() []T
	CurrentCopy() []T
	Next() bool
	Reset()
	SetDest([]T) error
}

type MultiPermutationGenerator 

type MultiPermutationGenerator[T any] struct {
	// contains filtered or unexported fields
}

MultiPermutationGenerator implements a Generator interface for generating multiset permutations by an algorithm described in MultiPermutations.

func NewMultiPermutationGenerator 

func NewMultiPermutationGenerator[T any](elems []T, reps []int) (*MultiPermutationGenerator[T], error)

NewMultiPermutationGenerator creates and initializes a new MultiPermutationGenerator. Arguments and returned errors are the same ones from the MultiPermutationGenerator.Init method.

func (*MultiPermutationGenerator[T]) Current 

func (gen *MultiPermutationGenerator[T]) Current() []T

Current returns the internal slice that holds the current permutation. If you need to modify the returned slice, use MultiPermutationGenerator.CurrentCopy instead.

func (*MultiPermutationGenerator[T]) CurrentCopy 

func (gen *MultiPermutationGenerator[T]) CurrentCopy() []T

CurrentCopy returns a copy of the internal slice that holds the current permutation. If you don't need to modify the returned slice, use MultiPermutationGenerator.Current to avoid allocation.

func (*MultiPermutationGenerator[T]) Init 

func (gen *MultiPermutationGenerator[T]) Init(elems []T, reps []int) error

Init initializes a generator of multiset permutations.

It accepts slices

  • elems: set of elements to make permutations from
  • reps: number of repetitions per element, rep must be 1 or higher.

Number of items in both slices must match, as reps correspond to the elems.

func (*MultiPermutationGenerator[T]) Next 

func (gen *MultiPermutationGenerator[T]) Next() bool

Next produces a new permutation in the generator. If it returns false, there are no more permutations available.

func (*MultiPermutationGenerator[T]) Reset 

func (gen *MultiPermutationGenerator[T]) Reset()

Reset resets the generator to the beginning of the sequence.

func (*MultiPermutationGenerator[T]) SetDest 

func (gen *MultiPermutationGenerator[T]) SetDest(dest []T) error

SetDest sets a destination slice that will receive the results. Returns an error if there's not enough capacity in the slice.

After the destination slice is set, subsequent calls to MultiPermutationGenerator.Current will return the provided slice.

type PermutationGenerator 

type PermutationGenerator[T any] struct {
	// contains filtered or unexported fields
}

PermutationGenerator implements a Generator interface for generating permutations by an algorithm described in Permutations.

func NewPermutationGenerator 

func NewPermutationGenerator[T any](elems []T) (*PermutationGenerator[T], error)

NewPermutationGenerator creates and initializes a new PermutationGenerator. Arguments and returned errors are the same ones from the PermutationGenerator.Init method.

func (*PermutationGenerator[T]) Current 

func (gen *PermutationGenerator[T]) Current() []T

Current returns the internal slice that holds the current permutation. If you need to modify the returned slice, use PermutationGenerator.CurrentCopy instead.

func (*PermutationGenerator[T]) CurrentCopy 

func (gen *PermutationGenerator[T]) CurrentCopy() []T

CurrentCopy returns a copy of the internal slice that holds the current permutation. If you don't need to modify the returned slice, use PermutationGenerator.Current to avoid allocation.

func (*PermutationGenerator[T]) Init 

func (gen *PermutationGenerator[T]) Init(elems []T) error

Init initializes a generator of permutations. Returns an error if input slice is nil or empty.

func (*PermutationGenerator[T]) Next 

func (gen *PermutationGenerator[T]) Next() bool

Next produces a new permutation in the generator. If it returns false, there are no more permutations available.

func (*PermutationGenerator[T]) Reset 

func (gen *PermutationGenerator[T]) Reset()

Reset resets the generator to the beginning of the sequence.

func (*PermutationGenerator[T]) SetDest 

func (gen *PermutationGenerator[T]) SetDest(dest []T) error

SetDest sets a destination slice that will receive the results. Returns an error if there's not enough capacity in the slice.

After the destination slice is set, subsequent calls to PermutationGenerator.Current will return the provided slice.

type VariationGenerator 

type VariationGenerator[T any] struct {
	// contains filtered or unexported fields
}

VariationGenerator implements a Generator interface for generating variations.

func NewVariationGenerator 

func NewVariationGenerator[T any](k int, elems []T) (*VariationGenerator[T], error)

NewVariationGenerator creates and initializes a new VariationGenerator. Arguments and returned errors are the same ones from the VariationGenerator.Init method.

func (*VariationGenerator[T]) Current 

func (gen *VariationGenerator[T]) Current() []T

Current returns the internal slice that holds the current variation. If you need to modify the returned slice, use VariationGenerator.CurrentCopy instead.

func (*VariationGenerator[T]) CurrentCopy 

func (gen *VariationGenerator[T]) CurrentCopy() []T

CurrentCopy returns a copy of the internal slice that holds the current variation. If you don't need to modify the returned slice, use VariationGenerator.Current to avoid allocation.

func (*VariationGenerator[T]) Init 

func (gen *VariationGenerator[T]) Init(k int, elems []T) error

Init initializes a generator for variations of size k out of elements in the elems slice. Returns an error if input slice is nil or empty, or if k < 1.

func (*VariationGenerator[T]) Next 

func (gen *VariationGenerator[T]) Next() bool

Next produces a new variation in the generator. If it returns false, there are no more variations available.

func (*VariationGenerator[T]) Reset 

func (gen *VariationGenerator[T]) Reset()

Reset resets the generator to the beginning of the sequence.

func (*VariationGenerator[T]) SetDest 

func (gen *VariationGenerator[T]) SetDest(dest []T) error

SetDest sets a destination slice that will receive the results. Returns an error if there's not enough capacity in the slice.

After the destination slice is set, subsequent calls to VariationGenerator.Current will return the provided slice.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.