英文:
How to properly copy arrays when using backtracking algorithm in Golang?
问题
我有一个简单的数组,值为[1, 2, 3],我想找出所有的排列组合。我不明白为什么将代码中的"复制"部分放在循环之前会导致程序出错。
当将复制操作放在循环之外时,结果如下:
[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 3 3] [3 3 3]]
当将复制操作放在循环之内时,结果如下:
[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
在第一个输出中,有两个数组的值为[3, 3, 3],这是错误的。
英文:
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
答案1
得分: 0
你说“我既不修改'c'也不修改'r',也不给它们追加内容”,这部分是正确的。
在循环的第一次迭代中,切片'c'和'curr'指向不同的后备数组,所以这是可以的。
但是当你稍后执行
curr = c
时,实际上是将两个切片都指向同一个后备数组。
这意味着在第二次迭代中,你的'append'操作可能会修改'c'和'curr'("可能"是因为调整大小会改变'curr'的后备数组)。
这就是导致你上面看到的奇怪行为的原因。
在Go语言中,切片有点棘手,所以当你知道你将对它们进行修改和传递时,最好避免赋值,而是完全复制它们(就像你在"WORKS"的情况下所做的那样)。
如果想进一步了解,这是一个不错的资源:https://go.dev/blog/slices-intro
英文:
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论