进行编程：生成组合

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