Go Programming: Generating Combinations

Question

This is homework

I'm working on a project, and a very small (very small, once I get this working...it's basically the pre-req for the rest of the project) part of it is to generate some combinations using a Go routine.

The code I have is thusly:

package bruteforce

// GenerateCombinations is an iterator function.  Given an alphabet and a
// length, it will generate every possible combination of the letters in
// alphabet of the specified length.
//
// It is meant to be consumed by using the range clause:
//
//  for combination := range GenerateCombinations(alphabet, length) {
//      process(combination)
//  }
//
func GenerateCombinations(alphabet string, length int) <-chan string {

GenerateCombinations(alphabet, length):
if length == 0:
    yield ""
else:
    for i := range alphabet{
        for j := range GenerateCombinations(alphabet, length-1){
            i + j
        }
    }

    return nil
}

I seriously do not get this at all. As you can see, there is some instructor-provided pseudo code there, but the implementation of it is frying my brain.

Example I/O would be something like this:

If the alphabet is {0, 1} and the password was length 2, then it would need to generate {0, 1, 00, 01, 10, 11}.

I appreciate all suggestions, but please recognize that the term "beginner" doesn't begin to describe my competency with go. Saying things like "use channels" doesn't help me at all. Explanations are my friend... something that I haven't had a lot of luck getting out of my professor aside from "use channels."

Answer 1

Your teacher has already hinted that you should use a channel instead of returning a big array. By solving it like that, you will not have to store this big chunk of data containing all combination, but rather feed your function with different iterations and process them one at a time.

We can see your teachers hint in that the GenerateCombinations returns a chan string and not a []string:

func GenerateCombinations(alphabet string, length int) <-chan string

This also means that the function must 1) create a channel to return, and 2) start a goroutine that feeds iterations to the channel. This function would look something like this:

func GenerateCombinations(alphabet string, length int) <-chan string {
    c := make(chan string)

    // Starting a separate goroutine that will create all the combinations,
    // feeding them to the channel c
    go func(c chan string) {
        defer close(c) // Once the iteration function is finished, we close the channel

        // This is where the iteration will take place
        // Your teacher's pseudo code uses recursion
        // which mean you might want to create a separate function
        // that can call itself.
    }(c)

    return c // Return the channel to the calling function
}

While I will leave the actual iteration to you, every loop should result in you putting a combination string into the channel. Because it is not a buffered channel, the iterating function will wait til the main function has read the value before continue to process the next iteration.

A playground version including the main function: http://play.golang.org/p/CBkSjpmQ0t

A full working solution using recursion: http://play.golang.org/p/0bWDCibSUJ

Answer 2

This is a tricky problem if you are entirely unfamiliar with Go and/or how to generate permutations. Below is a full implementation of the solution. I suggest you only look at this if you really get stuck, because doing so will obviously remove the learning experience.

You can run it on the go playground to see it work.

This approach is not recursive as your instructor's example suggests, but it gets the job done quite nicely.

package main

import "fmt"
import "sync"

func main() {
    // Make sure the alphabet is sorted.
    const alphabet = "abcde"

    for str := range generate(alphabet) {
        fmt.Println(str)
    }
}

func generate(alphabet string) <-chan string {
    c := make(chan string, len(alphabet))

    go func() {
        defer close(c)

        if len(alphabet) == 0 {
            return
        }

        // Use a sync.WaitGroup to spawn permutation
        // goroutines and allow us to wait for them all
        // to finish.
        var wg sync.WaitGroup
        wg.Add(len(alphabet))

        for i := 1; i <= len(alphabet); i++ {
            go func(i int) {
                // Perform permutation on a subset of
                // the alphabet.
                Word(alphabet[:i]).Permute(c)

                // Signal Waitgroup that we are done.
                wg.Done()
            }(i)
        }

        // Wait for all routines to finish.
        wg.Wait()
    }()

    return c
}

type Word []rune

// Permute generates all possible combinations of
// the current word. This assumes the runes are sorted.
func (w Word) Permute(out chan<- string) {
    if len(w) <= 1 {
        out <- string(w)
        return
    }

    // Write first result manually.
    out <- string(w)

    // Find and print all remaining permutations.
    for w.next() {
        out <- string(w)
    }
}

// next performs a single permutation by shuffling characters around.
// Returns false if there are no more new permutations.
func (w Word) next() bool {
    var left, right int

    left = len(w) - 2
    for w[left] >= w[left+1] && left >= 1 {
        left--
    }

    if left == 0 && w[left] >= w[left+1] {
        return false
    }

    right = len(w) - 1
    for w[left] >= w[right] {
        right--
    }

    w[left], w[right] = w[right], w[left]

    left++
    right = len(w) - 1

    for left < right {
        w[left], w[right] = w[right], w[left]
        left++
        right--
    }

    return true
}