1
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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{};
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.