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
}
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
combin-5.go
Description: Binary data
