Use of concurrency to generate combinations

Question

I have the following package to generate combinations from a slice of bytes:

//Package combinations generates combinations from a slice.
package combinations

//CombIter generates combinations of bytes of given length from a 
//list of elements. It returns values by a channel outC
//An empty list indicates that no further combinations are available
func CombIter(elements []byte, length int, outC chan []byte) {
    for i := 0; i < len(elements); i++ {
        if length == 1 {
            outC <- []byte{elements[i]}
        } else {
            inC := make(chan []byte)
            go combIter(elements[i+1:], length-1, inC)

            for next := <-inC; len(next) != 0; next = <-inC {
                outC<- append([]byte{elements[i]}, next...)
            }
        }
    }
    outC <- []byte{}
}

//Comb collects combinations of length k from a byte slice l.
//It returns a slice containing (len(l) C k) slices all of length k
func Comb(l []byte, k int) [][]byte {
    c := make(chan []byte)
    go combIter(l, k, c)
    o := [][]byte{}
    for next := <-c; len(next) != 0; {
        o = append(o, next)
        next = <-c
    }
    return o
}

I test it with

func TestComb(t *testing.T) 
    actual := Comb([]byte{'a', 'b', 'c', 'd'}, 2)
    expected := [][]byte{{'a', 'b'}, {'a', 'c'}, {'a', 'd'}, {'b', 'c'}, {'b', 'd'}, {'c', 'd'}}
    if !reflect.DeepEqual(actual, expected) {
        t.Errorf("Got  %v\nWant %v", actual, expected)
    }
}

The algorithm is an adaption of a python program: https://stackoverflow.com/a/2837693/2709093

I am particularly concerned with the use of concurrency, and the possibility of creating a disruptive number of goroutines. Is this a useful application of concurrency?

Answer 1

Go routines are cheap to make and run. So your solution would work perfectly fine.

To your question whether it's actually a useful application of concurrency I would say no. You're creating channels and go routines to then instantly wait for it's next result anyway.

Right below your linked python answer to that other question there's a nice java answer with a slightly different approach. I suggest combining the 2 approaches.

I'm not used to writing go code so the following will probably need a couple of fixes but should give you an idea how to do it correctly yourself:

func CombIter(input []byte, acc []byte, length int, outC chan []byte) {
    for i := 0; i < len(elements)-length+1; i++ {
        if length == 1 {
            outC <- append([]byte{acc, input[i]})
        } else {
            for j:= i+1; j < len(elements); j++ {
                combIter(input[j:], append([]byte{acc, input[j]}), length-1, inC)
            }
        }
    }
}

You might also have to check the stopping condition for the outer while loop. You want this one to stop when there aren't enough elements left to get a result of the correct length. I didn't run this code so it could be off by 1.

If you need that outC <- []byte{} line to have a stopping condition it may make most sense to provide a helper method:

func CombIter(input []byte, length int, outC chan []byte) {
    combIter(input, []byte{}, length, outC);
    outC <- []byte{};
}