gocombinatorics

README

gocombinatorics

Provides iterators for permutations and the like

Using

import "github.com/keep94/gocombinatorics"

Documentation

Overview

Package gocombinatorics contains routines useful for combinatorics.

Index

• type Stream
  • func Cartesian(sizes ...int) Stream
  • func Combinations(n, k int) Stream
  • func CombinationsWithReplacement(n, k int) Stream
  • func OpsPosits(k int) Stream
  • func Permutations(n, k int) Stream
  • func Product(n, k int) Stream

Types

type Stream

type Stream interface {

	// Next populates values with the next tuple and returns true.
	// If there are no more tuples, Next returns false and leaves values
	// unchanged. Caller must pass in a slice big enough to hold a tuple.
	Next(values []int) bool

	// TupleSize returns the size of tuples this stream emits. Caller must
	// pass a slice of at least this size to the Next method.
	TupleSize() int

	// Reset resets this stream to the state it had when it was first created.
	// After calling Reset, Next will yield the first tuple.
	Reset()
}

Stream represents a finite stream of tuples

func Cartesian

func Cartesian(sizes ...int) Stream

Cartesian returns the cartesian product of (0, 1, 2, ..., s0-1), (0, 1, 2, ..., s1-1), (0, 1, 2, ..., s2-1) etc. For instance, Cartesian(3, 2, 4) yields (0,0,0), (0,0,1), (0,0,2), (0,0,3), (0,1,0), (0,1,1), (0,1,2), (0,1,3), (1,0,0), (1,0,1), (1,0,2), (1,0,3), (1,1,0), (1,1,1), (1,1,2), (1,1,3), (2,0,0), (2,0,1), (2,0,2), (2,0,3), (2,1,0), (2,1,1), (2,1,2), (2,1,3)

func Combinations

func Combinations(n, k int) Stream

Combinations yields all the ways you can pick k ints from 0 to n-1 inclusive where order does not matter. The returned Stream's Next method will yield k-tuples.

For instance, Combinations(4,2) yields (0,1), (0,2), (0,3), (1,2), (1,3), (2,3)

func CombinationsWithReplacement

func CombinationsWithReplacement(n, k int) Stream

CombinationsWithReplacement is like Combinations except that returned tuples may contain duplicates. For instance, CombinationsWithReplacement(4, 2) yields (0,0), (0,1), (0,2), (0,3), (1,1), (1,2), (1,3), (2,2), (2,3), (3,3)

func OpsPosits

func OpsPosits(k int) Stream

OpsPosits yields all the possible positions of k binary operators in a postfix expression as a sequence of k-tuples. A value of 0 means the operator comes after the first number; 1 means the operator comes after the second number etc. Each value in a tuple is the same or greater than the previous value. Moreover the 1st value in a tuple must be at least 1; the 2nd value in a tuple must be at least 2 etc. None of the values in a tuple can be greater than k.

For instance, OpsPosits(4) yeilds (1,2,3,4), (1,2,4,4), (1,3,3,4), (1,3,4,4), (1,4,4,4), (2,2,3,4) (2,2,4,4), (2,3,3,4), (2,3,4,4), (2,4,4,4), (3,3,3,4), (3,3,4,4) (3,4,4,4), (4,4,4,4)

func Permutations

func Permutations(n, k int) Stream

Permutations yields all the ways you can pick k ints from 0 to n-1 inclusive where order matters. The returned Stream's Next method will yield k-tuples.

For instance, Permutations(4,2) yields (0,1), (0,2), (0,3), (1,0), (1,2), (1,3), (2,0), (2,1), (2,3), (3,0), (3,1), (3,2)

func Product

func Product(n, k int) Stream

Product is like Permutations except that the returned tuples may contain duplicates. For instance, Product(3, 2) yields (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)