Documentation
¶
Index ¶
- type CombinationColexIterator
- type CombinationIterator
- type IntegerPartitionIterator
- type LexicographicPermutationIterator
- type MultisetCombinationIterator
- type MultisetPermutationIterator
- type PartitionIterator
- type PermutationIterator
- type PermutationsByPatternIterator
- type ProductIterator
- type RestrictedPrefixPermutationIterator
- type RestrictedPrefixProductIterator
- type TopologicalSortIterator
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CombinationColexIterator ¶
type CombinationColexIterator struct {
// contains filtered or unexported fields
}
CombinationColexIterator iterates over all ways of chooding k elements from 0, ..., n-1 in colexicographic order. It can be initialised by calling CombinationsColex.
func CombinationsColex ¶
func CombinationsColex(n, k int) *CombinationColexIterator
CombinationsColex returns a new CombinationColexIterator which iterates over all subsets of k distinct elements from 0, ..., n-1 in colexicographic order.
func (*CombinationColexIterator) Next ¶
func (b *CombinationColexIterator) Next() bool
Next attempts to advance the iterator to the next subset, returning true if there is one and false if not.
func (CombinationColexIterator) Value ¶
func (b CombinationColexIterator) Value() []int
Value returns the current subset. The output must not be modified.
type CombinationIterator ¶
type CombinationIterator struct {
// contains filtered or unexported fields
}
CombinationIterator iterates over all ways of choosing k elements from 0, ..., n-1 in lexicographic order.
func Combinations ¶
func Combinations(n, k int) *CombinationIterator
Combinations returns a new CombinationIterator which iterates over all subsets of k distinct elements from 0, ..., n-1 in lexicographic order.
func (*CombinationIterator) Next ¶
func (b *CombinationIterator) Next() bool
Next moves the Iterator to the next combination, returning true if there is one and false is there isn't.
func (CombinationIterator) Value ¶
func (b CombinationIterator) Value() []int
Value returns the current state of the iterator. This must not be modified.
type IntegerPartitionIterator ¶
type IntegerPartitionIterator struct {
// contains filtered or unexported fields
}
IntegerPartitionIterator iterates over all ways of writing n as the sum of positive integers in descending order. The integer partitons are generated in reverse lexicographic order.
func IntegerPartitions ¶
func IntegerPartitions(n int) *IntegerPartitionIterator
IntegerPartitions returns an *IntegerPartitionIterator for iterating over all ways of writing n as the sum of positive integers in descending order. The integer partitons are generated in reverse lexicographic order.
func (*IntegerPartitionIterator) Next ¶
func (iter *IntegerPartitionIterator) Next() bool
Next tries to advance iter to the next integer partition, returning true if there is one and false if there isn't.
func (IntegerPartitionIterator) Value ¶
func (iter IntegerPartitionIterator) Value() []int
Value returns the current integer partition. It is not safe to modify the output
type LexicographicPermutationIterator ¶
type LexicographicPermutationIterator struct {
// contains filtered or unexported fields
}
LexicographicPermutationIterator is a struct contraining the state of an iterator which iterates over all permutations of {0, 1, ..., n-1} in lexicographic order.
func LexicographicPermutations ¶
func LexicographicPermutations(n int) *LexicographicPermutationIterator
LexicographicPermutations returns a new iterator which iterates over all permutations of {0, ..., n-1} in lexicographic order. It is not safe to modify the output of the iterator.
func (*LexicographicPermutationIterator) Next ¶
func (iter *LexicographicPermutationIterator) Next() bool
Next moves the iterator to the next permutation, returning true if there is one and false if the previous permutation is the last one.
func (*LexicographicPermutationIterator) Value ¶
func (iter *LexicographicPermutationIterator) Value() []int
Value returns the current permutation. You must not modify the output of this function.
type MultisetCombinationIterator ¶ added in v0.2.0
type MultisetCombinationIterator struct {
// contains filtered or unexported fields
}
MultisetCombinationIterator iterates over all multisets containing k elements and with a maximum of m[i] copies of i. Value returns the multiset of k elements and FreqValue returns a slice v where v[i] is the number of copies of i in the multiset.
func MultisetCombinations ¶ added in v0.2.0
func MultisetCombinations(m []int, k int) *MultisetCombinationIterator
MultisetCombinations returns an iterator which iterates over all multisets containing k elements and with a maximum of m[i] elements of type i. Value returns the multiset of k items and FreqValue returns a slice v where v[i] is the number of i in the multiset.
func (MultisetCombinationIterator) FreqValue ¶ added in v0.2.0
func (iter MultisetCombinationIterator) FreqValue() []int
FreqValue returns a slice v where v[i] is the number of i in the multiset. You must not modify the return value.
func (*MultisetCombinationIterator) Next ¶ added in v0.2.0
func (iter *MultisetCombinationIterator) Next() bool
Next attempts to advance the iterator to the next multiset, returning true if there is one and false if not. This is an implementation of Algorithm Q from The Art of Computer Programming Volume 4a section 7.2.1.3.
func (MultisetCombinationIterator) Value ¶ added in v0.2.0
func (iter MultisetCombinationIterator) Value() []int
Value returns the multiset of k elements. You may modify the return value.
type MultisetPermutationIterator ¶
type MultisetPermutationIterator struct {
// contains filtered or unexported fields
}
MultisetPermutationIterator is a struct containing the state of an iterator which iterates over all permutations of some multiset from {0, 1, ..., n-1} in lexicographic order.
func MultisetPermutations ¶
func MultisetPermutations(freq []int) *MultisetPermutationIterator
MultisetPermutations returns an iterator which iterates over all permutations of some multiset from {0, 1, ..., n-1} in lexicographic order. The number i appears freq[i] times in the multiset. It is not safe to modify the output of the iterator.
func (*MultisetPermutationIterator) Next ¶
func (iter *MultisetPermutationIterator) Next() bool
Next moves the iterator to the next permutation, returning true if there is one and false if the previous permutation is the last one.
func (*MultisetPermutationIterator) Value ¶
func (iter *MultisetPermutationIterator) Value() []int
Value returns the current permutation. You must not modify the output of this function.
type PartitionIterator ¶
type PartitionIterator struct {
// contains filtered or unexported fields
}
PartitionIterator iterates over all partitions of the set {0, ..., n-1}. The partitions are generated in lexicographic order of their restricted growth strings. It is safe to modify the output of .Value().
func Partitions ¶
func Partitions(n int) *PartitionIterator
Partitions returns a *PartitionIterator which iterates over all partitions of the set {0, ..., n-1}. The partitions are generated in lexicographic order of their restricted growth sequences. TODO Handle n = 0
func (*PartitionIterator) Next ¶
func (pi *PartitionIterator) Next() bool
Next tries to advance pi to the next partition, returning true if there is one and false if there isn't.
func (PartitionIterator) Value ¶
func (pi PartitionIterator) Value() [][]int
Value returns the current partition. It is safe to modify the output, although one shouldn't depend on this.
type PermutationIterator ¶
type PermutationIterator struct {
// contains filtered or unexported fields
}
PermutationIterator is a struct containing the state of the iterator. It iterates over permutations according to Heap's algorithm.
func Permutations ¶
func Permutations(n int) *PermutationIterator
Permutations returns a new permuation iterator which iterates over all permutations of the elements {0, ..., n - 1}.
func (*PermutationIterator) Next ¶
func (p *PermutationIterator) Next() bool
Next moves the iterator to the next permutation, returning true if there is one and false if the previous permutation is the last one.
func (*PermutationIterator) Value ¶
func (p *PermutationIterator) Value() []int
Value returns the current permutation. You must not modify the output of this function.
type PermutationsByPatternIterator ¶ added in v0.2.0
type PermutationsByPatternIterator struct {
// contains filtered or unexported fields
}
PermutationsByPatternIterator holds the state for an iterator which iterates over all permutations which pass a test function at every step.
func PermutationsByPattern ¶ added in v0.2.0
func PermutationsByPattern(n int, f func([]int) bool) *PermutationsByPatternIterator
PermutationsByPattern iterates over all permutations of {0, 1, ..., n -1} which pass the test function f at every step. The iterator starts with the empty permutation. It then does a DFS where the children of a permutation P of length l < n are the permutations of length l + 1 formed by appending a number x in {0, ..., l} and increasing by 1 every entry of P which is at least x. The function f is called at each node of the DFS and the iterator will prune the children of a node v if f(v) is false.
func (*PermutationsByPatternIterator) Next ¶ added in v0.2.0
func (iter *PermutationsByPatternIterator) Next() bool
Next attempts to move to the next valid permutation, returning true if one exists and false otherwise.
func (*PermutationsByPatternIterator) Value ¶ added in v0.2.0
func (iter *PermutationsByPatternIterator) Value() []int
Value returns the current permutation. You must not modify the returned value.
type ProductIterator ¶
type ProductIterator struct {
// contains filtered or unexported fields
}
ProductIterator iterates over {0, ..., n[0] - 1} x {0, ..., n[1] - 1} x ... x {0, ..., n[len(n) - 1] - 1}. It should be initliased using Product.
func Product ¶
func Product(n ...int) *ProductIterator
Product returns a *ProductIterator to iterate over {0, ..., n[0] - 1} x {0, ..., n[1] - 1} x ... x {0, ..., n[len(n) - 1] - 1}.
func (*ProductIterator) Next ¶
func (p *ProductIterator) Next() bool
Next attempts to move the iterator to the next state, returning true if there is one and false if there isn't.
func (ProductIterator) Value ¶
func (p ProductIterator) Value() []int
Value returns the current state of the iterator. It isn't safe to modify the state.
type RestrictedPrefixPermutationIterator ¶ added in v0.2.0
type RestrictedPrefixPermutationIterator struct {
// contains filtered or unexported fields
}
RestrictedPrefixPermutationIterator iterates over all permutations a_1 a_2 ... a_n of {0, ..., n-1} which pass the tests f([]int{a_1}), f([]int{a_1,a_2}) ... f([]int{a_1,...,a_n}). It iterates over the allowed permutations in lexicographic order.
func RestrictedPrefixPermutations ¶ added in v0.2.0
func RestrictedPrefixPermutations(n int, f func([]int) bool) *RestrictedPrefixPermutationIterator
RestrictedPrefixPermutations returns an iterator which iterates over all permutations a_1 a_2 ... a_n of {0, ..., n-1} which pass the tests f([]int{a_1}), f([]int{a_1,a_2}) ... f([]int{a_1,...,a_n}). It iterates over the allowed permutations in lexicographic order.
func (*RestrictedPrefixPermutationIterator) Next ¶ added in v0.2.0
func (iter *RestrictedPrefixPermutationIterator) Next() bool
Next attempts to advance the iterator to the next allowed permutation, returning true if there is one and false otherwise.
func (*RestrictedPrefixPermutationIterator) Value ¶ added in v0.2.0
func (iter *RestrictedPrefixPermutationIterator) Value() []int
Value returns the current permutation. You must not modify the value.
type RestrictedPrefixProductIterator ¶ added in v0.2.0
type RestrictedPrefixProductIterator struct {
// contains filtered or unexported fields
}
RestrictedPrefixProductIterator iterates over all elements (a_0, a_1, ..., a_{len(n)-1}) of {0, ..., n[0] - 1} x {0, ..., n[1] - 1} x ... x {0, ..., n[len(n) - 1] - 1} which pass the tests f(a_0), f(a_0, a_1), ... If len(n) == 0, then the value []int{} is considered to pass.
func RestrictedPrefixProduct ¶ added in v0.2.0
func RestrictedPrefixProduct(t func([]int) bool, n ...int) *RestrictedPrefixProductIterator
RestrictedPrefixProduct returns a *RestrictedPrefixProductIterator which iterates over all elements (a_0, a_1, ..., a_{len(n)-1}) of {0, ..., n[0] - 1} x {0, ..., n[1] - 1} x ... x {0, ..., n[len(n) - 1] - 1} which pass the test f(a_0), f(a_0, a_1), ...
func (*RestrictedPrefixProductIterator) Next ¶ added in v0.2.0
func (p *RestrictedPrefixProductIterator) Next() bool
Next attempts to move the iterator to the next state, returning true if there is one and false if there isn't.
func (RestrictedPrefixProductIterator) Value ¶ added in v0.2.0
func (p RestrictedPrefixProductIterator) Value() []int
Value returns the current value of the iterator. You must not modify the value.
type TopologicalSortIterator ¶
type TopologicalSortIterator struct {
// contains filtered or unexported fields
}
TopologicalSortIterator iterates over all topological sorts of {0, 1, ..., n-1} respecting some partial order of the total order 0 < 1 < ... < n -1.
func TopologicalSorts ¶
func TopologicalSorts(n int, less func(i, j int) bool) *TopologicalSortIterator
TopologicalSorts returns an iterator which iterates over all topological sorts of {0, 1, ... , n-1} according to the partial order less. If less(i,j) == true, then this only iterates over permutations where i appears before j. less must be a sub-order of the total order 0 < 1 < ... n -1 i.e. for inputs i < j the function less should return true if the condition i < j should be imposed and false otherwise. If i >= j, the function should return false. The function less doesn't need to be transitive as if i < j < k, then less(i,k) will never be called. If less(i,j) == true, then the inverse permutation is such that the value in position i is smaller than the value in position j. The function iter.InverseValue() returns the inverse permutation.
func (*TopologicalSortIterator) InverseValue ¶
func (iter *TopologicalSortIterator) InverseValue() []int
InverseValue returns the inverse the to current permutation. You must not modify the value.
func (*TopologicalSortIterator) Next ¶
func (iter *TopologicalSortIterator) Next() bool
Next attempts to advance the iterator to the next permutation, returning true if there is one and false otherwise.
func (*TopologicalSortIterator) Value ¶
func (iter *TopologicalSortIterator) Value() []int
Value returns the current permutation. You must not modify the value.
Source Files