Go programming exercise: generating all combinations of an alphabet of symbols

combos

See https://forum.golangbridge.org/t/generation-of-strings-generation/2968/2

drd0s.go

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
}

main.go

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)
}

main_test.go

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)
}

meta.go

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
}

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