Permutation generator based on group theory1.
- Fast
- Stateless
- generate next permutation from current permutation only.
- Permutation order is NOT lexical.
go get github.com/deltam/perm
Index only:
func main() {
g, err := perm.New(3)
if err != nil {
log.Fatal(err)
}
for ; !g.Done(); g.Next() {
fmt.Println(p)
}
}
// Output:
// [1 2 0]
// [2 0 1]
// [0 2 1]
// [2 1 0]
// [0 1 2]
// [1 0 2]
Permutation of slice:
func main() {
words := []rune("ABC")
g, err := perm.Iter(ss)
if err != nil {
log.Fatal(err)
}
for ; !g.Done(); g.Next() {
fmt.Printf("%v\t%s\n", g.Index(), string(words))
}
}
// Output:
// [1 2 0] ABC
// [2 0 1] BCA
// [0 2 1] CBA
// [2 1 0] BAC
// [0 1 2] CAB
// [1 0 2] ACB
This algorithm is 40~50% faster than naive recursive algorithm.
time/op | |
---|---|
Primitive-8 | 33.3µs ± 2% |
Generator-8 | 39.1µs ± 2% |
PermRecursive-8 | 66.9µs ± 1% |
func recPerm(p []int, n int, ignore []bool) {
if n == 0 {
return
}
for i := 0; i < len(p); i++ {
if !ignore[i] {
p[n-1] = i
ignore[i] = true
recPerm(p, n-1, ignore)
ignore[i] = false
}
}
}
I also explained details on my blog post(Japanese only). 2
Cayley graph on permutation group generated by sigma and tau has a size two disjoint cycle cover and Hamilton path.
sigma(rotation): (1, 2, ..., n) -> (2, 3, ..., n, 1)
tau(swap): (1, 2, ..., n) -> (2, 1, ..., n)
Below is the Hamilton path created by split and join the two cycles.
By observing above Hamilton path, you can discover local rule for generating that.
See primitive.go
or this text32 for details.
MIT
Copyright 2019 deltam