I've been working on a project that requires me to generate all of the possible tuples of a specific length from a set of (complex) numbers. To do this, I tried implementing a version of the Mathematica Tuples[] command, but found that it was not generating all tuples correctly.
After much frustration, I found that when my program was generating tuples of length 4 it would add duplicates instead of new elements, leading to problems for any tuples of any longer length. I looked online to see if anyone had any other similar issues, and then found some other code to accomplish the same task, and noticed my solution was similar to theirs. I could not tell where I had gone wrong.
After even more frustration, I found that if I prepended the elements to the list everything worked fine, and only appending was the issue. I have tried to figure out what is wrong with my original code, and have come up with nothing.
Below is the code I made to demonstrate the issue. I'm by no means a professional coder, so you'll have to forgive me if this isn't the most idiomatic way of accomplishing this task. At the moment I'm using the tuplesByPrepend function in my actual code and it's working just fine, I'm really just hoping to understand what has gone wrong with the tuplesByAppend function. Again, at the third, fifth, eighth, and any other level I've tested it seems to be doing fine. I can provide more information on my OS and build and all that if need be.
package main
import "fmt"
func tuplesByAppend[T any](list []T, depth int) [][]T {
var l1 [][]T
var l2 [][]T
for _, v := range list {
l1 = append(l1, []T{v})
}
for i := 1; i < depth; i++ {
for _, u := range l1 {
for _, v := range list {
// Differs here
next := append(u, v)
// next is calculated properly, but added to l2 incorrectly at the fourth level only
// at the fifth level it functions properly
// fmt.Println(next)
l2 = append(l2, next)
// fmt.Println(l2)
// it appears that at the fourth level it is writing over the previous entries
// Printing here yields
// [[1 1 1 1]]
// [[1 1 1 2] [1 1 1 2]]
// [[1 1 1 3] [1 1 1 3] [1 1 1 3]]
// [[1 1 1 3] [1 1 1 3] [1 1 1 3] [1 1 2 1]]
// [[1 1 1 3] [1 1 1 3] [1 1 1 3] [1 1 2 2] [1 1 2 2]]
// and so on.
}
}
l1 = l2
l2 = [][]T{}
}
return l1
}
func tuplesByPrepend[T any](list []T, depth int) [][]T {
var l1 [][]T
var l2 [][]T
for _, v := range list {
l1 = append(l1, []T{v})
}
for i := 1; i < depth; i++ {
for _, u := range l1 {
for _, v := range list {
// Differs here
next := append([]T{v}, u...)
l2 = append(l2, next)
}
}
l1 = l2
l2 = [][]T{}
}
return l1
}
func main() {
ourlist := []int{1, 2, 3}
ourdepth := 4
appended := tuplesByAppend(ourlist, ourdepth)
prepended := tuplesByPrepend(ourlist, ourdepth)
// We should expect this slice to start [1 1 1 1] [1 1 1 2] [1 1 1 3] [1 1 2 1] ...
// In fact, it starts [1 1 1 3] [1 1 1 3] [1 1 1 3] [1 1 2 3]
fmt.Println(appended)
// This slice is as expected
fmt.Println(prepended)
}
The following line does not work as what you expected in some cases:
next := append(u, v)
This example demonstrates what happens:
package main
import "fmt"
func main() {
u := append([]int{1, 2}, 3)
// The length is 3 but the capacity is 4.
fmt.Printf("u %v\n len: %d\n cap: %d\n", u, len(u), cap(u))
// Since u has enough capacity for the new element "4",
// v1 will share the same underlying array.
v1 := append(u, 4)
fmt.Println("v1:", v1)
// As what happened to v1, v2 will share the same underlying array too.
// But the last element "4" in the underlying array is changed to "5".
v2 := append(u, 5)
fmt.Println("v2:", v2)
// Since v1 uses the same underlying array, it sees the change in the last step.
fmt.Println("v1:", v1)
}
To prevent it from sharing the underlying array, replace next := append(u, v) with the following code:
next := make([]T, len(u)+1)
copy(next, u)
next[len(u)] = v
See Go Slices: usage and internals for more information.