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."

Banish

All of this is instructor-provided code. Which is part of my confusion. – Banish

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

Di

This is really helpful! Thank you! Can I take your response to mean that if I fill in the code where you commented for iteration, that I may have working code? Or is there still more that I've got to figure out? – Banish

You have to add the iteration part (I added a comment about the recursion your teacher is hinting at). You might want to have a main function calling and listening to the channel as well. Hmm.. okay, I'll add that part as well. – Di

If you need more hints and help on how to create a recursive function, just add a comment. But this should at least get you started :) . And remember to accept the answer if it was useful. – Di

Yeah this was tremendously helpful, thank you very much. One thing I'm a little confused on, when you suggest making another function for recursion, would that look something like: func fooCursion (foo bar) <- chan string { } ? – Banish

And actually, where the iteration happens, is that where I use the range clause? – Banish

@Joodoo The function would take the channel as parameter so it can write to it while generating the combinations. Regarding the placement of the range clause: Just look at ANisus' comments in the code, they basically tell you that. – Verecund

@Joodoo Inspired by Jimt, I've added a playground link to a working example of the recursion solution. You can use the code if, and only if, you understand what it does ;) . There are other ways to solve it, but that is probably how your teacher would do it. – Di

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
}

Milling

This is super useful as well, I plan to use a few lines in my code, if that's alright with you. Cited of course. Looking at completed code helps me understand what is happening as opposed to the provided pseudo code, which doesn't really get me anywhere. – Banish

No problem. Looking at complete, working samples is the best way for me to learn as well. – Milling

Nice permutation solution :) . But, looking at Joodoo's example, the teacher wants Permutation with repetition while yours is without repetition. I think it is for generating a password brute force application. – Di

Answer 3

For these tasks you can try the Iterium package: https://github.com/mowshon/iterium#user-content-combinatorics

product := iterium.Product([]string{"A", "B", "C", "D"}, 2)
toSlice, _ := product.Slice()

fmt.Println("Total:", product.Count())
fmt.Println(toSlice)

Mosley