I have a simple array with values [1, 2, 3], and I'd like to find all permutations. I don't understand why moving 'copying' part of the code before the loop breaks the program.
func generatePermutations(curr, remains []int) [][]int {
if len(remains) == 0 {
return [][]int{curr}
}
var res [][]int
// DOESN'T WORK
c, r := make([]int, len(curr)), make([]int, len(remains))
copy(c, curr)
copy(r, remains)
for i := 0; i < len(remains); i++ {
// WORKS
//c, r := make([]int, len(curr)), make([]int, len(remains))
//copy(c, curr)
//copy(r, remains)
curr = append(curr, remains[i])
res = append(res, generatePermutations(curr, append(append(remains[:i]), remains[i+1:]...))...)
curr = c
remains = r
}
return res
}
When copy is outside the loop the result is the following: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 3 3] [3 3 3]]
When copy is inside the loop the result is the following: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
In the first output there are two arrays with [3,3,3] which is wrong
You say that I neither modify "c" or "r" nor append to them, which is partially true.
In the first iteration of the loop,
the slices c and curr point to different backing arrays, so this is fine.
But when you do
curr = c
a bit later, you're actually assigning both slices to point to the same backing array.
This means that on the second iteration, your append could modify both c and curr ("could" because a resize would change the backing array for curr).
This is what's causing the strange behavior you see above.
Slices in go are a bit tricky, so when you know you'll be mutating and passing them around, it's better to avoid assignments, but rather stick to copying them entirely (as you do in the "WORKS" case).
For further reading this is a nice resource: https://go.dev/blog/slices-intro