Skip to content

Instantly share code, notes, and snippets.

@lpar
Last active Jul 13, 2016
Embed
What would you like to do?
Go programming exercise: generating all combinations of an alphabet of symbols
See https://forum.golangbridge.org/t/generation-of-strings-generation/2968/2
package main
func GenerateCombinations(alphabet string, length int) <-chan string {
c := make(chan string)
go func(c chan string) {
defer close(c)
AddLetter(c, "", alphabet, length)
}(c)
return c
}
func AddLetter(c chan string, combo string, alphabet string, length int) {
if length <= 0 {
return
}
var newCombo string
for _, ch := range alphabet {
newCombo = combo + string(ch)
c <- newCombo
AddLetter(c, newCombo, alphabet, length-1)
}
}
func AssembleCombinations(alphabet string, length int) []string {
a := []string{}
for combination := range GenerateCombinations(alphabet, length) {
if len(combination) == length {
a = append(a, combination)
}
}
return a
}
package main
import "fmt"
func main() {
x := genall("abc", 3)
fmt.Printf("meta: %+v\n", x)
y := AssembleCombinations("abc", 3)
fmt.Printf("drd0s: %+v\n", y)
}
package main
import (
"testing"
)
func BenchmarkMetaSmall(b *testing.B) {
_ = genall("abcdefg", 6)
}
func BenchmarkDrd0sSmall(b *testing.B) {
_ = AssembleCombinations("abcdefg", 6)
}
func BenchmarkMetaLarge(b *testing.B) {
_ = genall("abcdefghi", 8)
}
func BenchmarkDrd0sLarge(b *testing.B) {
_ = AssembleCombinations("abcdefghi", 8)
}
package main
import (
"fmt"
"math"
"strings"
)
func inc(itoa []byte, atoi []int, x []byte) error {
carry := 1
i := len(x)
for carry == 1 {
i--
c := x[i]
av := atoi[int(c)]
av += carry
if av >= len(itoa) {
av = 0
carry = 1
if i == 0 {
return fmt.Errorf("overflow")
}
} else {
carry = 0
}
x[i] = itoa[av]
}
return nil
}
func genall(alphabet string, length int) []string {
// Turn the alphabet into a byte array so we can speedily go from an index value to a byte
itoa := []byte(alphabet)
// We also need to do the reverse, so make a byte array for that too
atoi := make([]int, 256)
for i, v := range itoa {
atoi[int(v)] = i
}
// Make our initial value
a := []byte(strings.Repeat(string(itoa[0:1]), length))
// And space for the results
n := int(math.Pow(float64(len(alphabet)), float64(length)))
combos := make([]string, 0, n)
// Print and increment until overflow
var err error
for err == nil {
combos = append(combos, string(a))
err = inc(itoa, atoi, a)
}
return combos
}
@lpar
Copy link
Author

lpar commented Jul 13, 2016

Benchmarks on my machine:

BenchmarkMetaSmall-8    2000000000           0.00 ns/op
BenchmarkDrd0sSmall-8   2000000000           0.04 ns/op
BenchmarkMetaLarge-8           1    2590756220 ns/op
BenchmarkDrd0sLarge-8          1    40684782719 ns/op

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment