Calculation of the combinations between an unlimited number of slices

[fred.so...@gmail.com]

Hi !

I have made a recursive algorithm to compute all the combinations between an unlimited number of slices. The algorithm does good results for 2 and 3 slices.

For example with 3 slices a,b,c :

a := []int{1,2}

b := []int{3,4}

c := []int{5,6}

final comb [[1 3 5] [1 3 6] [1 4 5] [1 4 6] [2 3 5] [2 3 6] [2 4 5] [2 4 6]] // good

, but I have a strange bug with 4 slices : only the last element of the slice 4 is recorded.

    a := []int{1,2}

    b := []int{3,4}

    c := []int{5,6}

    d := []int{7,8,9}

final comb [[1 3 5 9] [1 3 5 9] [1 3 5 9] [1 3 6 9] [1 3 6 9] [1 3 6 9] [1 4 5 9] [1 4 5 9]

[1 4 5 9] [1 4 6 9] [1 4 6 9] [1 4 6 9] [2 3 5 9] [2 3 5 9] [2 3 5 9] [2 3 6 9] [2 3 6 9]

[2 3 6 9] [2 4 5 9] [2 4 5 9] [2 4 5 9] [2 4 6 9] [2 4 6 9] [2 4 6 9]]

// bad result, the combination [1 3 5 7] and [1 3 5 8] are missing

The error occurs between these 2 steps

c1 := append(c, s)

temp = append(temp, c1)

when  c1 is appended to temp, 

i,j,k = 2, 0, 0 - temp = [[1 3 5 7]]

 [[1 3 5 7]] is replaced by [1 3 5 8] inside the loop and [1 3 5 7] combination is lost !

i,j,k =2, 0, 1 - temp = [[1 3 5 8] [1 3 5 8]]

i,j,k =2, 0, 2 - temp = [[1 3 5 9] [1 3 5 9] [1 3 5 9]]

Here is the algorithm. With 5 slices the results are good except for the slice 4 combinations. I did not found the bug, if you see it,  thank you for your help !

package main

import (

    "fmt"

)

func main() {

    a := []int{1,2}

    b := []int{3,4}

    c := []int{5,6}

    d := []int{7,8,9}

    //e := []int{1,2}   

    

    seq := [][]int{a, b, c, d} // slice to combine with comb [[b1 b2] [c1 c2 c3]]

    fmt.Println("final comb ", combIntSlices(seq) )

}

// function to build the combinations

func combIntSlices(seq [][]int) (out [][]int) {

    

        // fill combSeq with the first slice of seq

        var combSeq [][]int // combSeq is the initial [][]int, for example [[1] [2] [3]]

        for _, i := range seq[0] {

            combSeq = append(combSeq, []int{i})

        }

    

        seq = seq[1:] // seq is the [][]slice to combine with combSeq [[4 5] [6 7 8]]

        fmt.Println(seq, len(seq))

        // rec recursive funtion

        var rec func(int, [][]int, [][]int)

        rec = func(i int, seq, combSeq [][]int) {

    

            var temp [][]int // temporary slice to append combinations

            last := len(seq) - 1

    

            fmt.Println(combSeq, "-", seq)

            for j, c := range combSeq { // for each slice in combSeq slice

                for k, s := range seq[i] { // append each element of the slice i in seq

                    c1 := append(c, s)

                    temp = append(temp, c1)

                    fmt.Println(i,j,k, "- temp =", temp, " c=", c)

                }

                combSeq = temp // at this step temp has recorded one round of combination

            }

            if i == last { // if the length of seq is reached, the solution is returned

                out = combSeq

                return

            } else {

                rec(i+1, seq, combSeq) // if the length of seq is not reached, rec is called to perform another step of combinations

            }

        }

        rec(0, seq, combSeq) // start the first step of combinations

        return out

    }

[Fred]

it seems that making a copy of the temp var, replacing :

temp = append(temp, c1)

by :

temp = append(temp, append([]int{}, c1...))

helps, but still unclear for me why the problem was only visible on slice 4...

[jake...@gmail.com]

Perhaps start with Go Slices: usage and internals, for a more complete understanding of slice pitfalls.

[Fred]

Thanks @Jake

[howar...@gmail.com]

When you use append, two different things can happen:

1. There is enough capacity in the original slice to which you are appending to add the additional values. You get a slice that points to the same backing memory.

2. There is not enough capacity in the original slice to which you are appending. You get a slice that points to a newly allocated chunk of backing memory.

This blog talks specifically about append: https://blog.golang.org/slices

Now, looking at your code:

 

    c1 := append(c, s)
    temp = append(temp, c1)
    fmt.Println(i,j,k, "- temp =", temp, " c=", c)

The key thing to see here, is that s is going to be added to c, and *c* is going to end up in c1, IF there is enough room for s in c. So, sometimes c1 is pointing to the same bit of memory as c, sometimes a different bit.

I think, rather than making a copy of the temp variable c1, you should be doing the same thing at the step where you create c1.

In other words, something like

c1 := append([]int{}, c..., s)

[Fred]

@Howard thank you very much for this nice analysis of my code !