在使用回溯算法时,如何正确地复制数组?

huangapple go评论79阅读模式
英文:

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

huangapple
  • 本文由 发表于 2022年12月21日 14:57:13
  • 转载请务必保留本文链接:https://go.coder-hub.com/74872299.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定