在Golang中使用回溯演算法時如何正確複製數組？

在Golang中使用回溯演算法時，正確複製陣列是一個重要的問題。回溯演算法通常需要在遞歸過程中對陣列進行修改，但有時我們需要保存原始陣列的狀態以便回溯到上一步。在這種情況下，我們不能簡單地將原始數組直接賦值給一個新變量，因為它們共享同一塊記憶體空間，修改一個數組會影響到另一個數組。解決這個問題的方法是使用深拷貝，即創建一個新的數組並將原始數組的值依次複製到新數組中。在Golang中，可以使用copy()函數來完成這個操作，它會以位元組層級複製數組的內容，確保新數組和原始數組完全獨立。透過正確複製數組，我們可以在回溯演算法中安全地操作數組，而不會影響到原始資料的狀態。

問題內容

我有一個帶有值 [1, 2, 3] 的簡單數組，我想找到所有排列。我不明白為什麼在循環中斷程序之前移動“複製”部分程式碼。

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
}

當複製位於循環之外時，結果如下： [[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] 的數組，這是錯誤的

解決方法

你說我既不修改“c”或“r”也不附加到它們，這部分是正確的。

在循環的第一次迭代中， 切片 c 和 curr 指向不同的支援數組，所以這很好。

但是當你這麼做的時候

curr = c

稍後，您實際上將兩個切片指派為指向同一個支援陣列。

這表示在第二次迭代中，您的append 可以修改curr 和curr （“可以”，因為調整大小會改變curr 的支援數組）。

這就是導致您在上面看到的奇怪行為的原因。

go 中的切片有點棘手，所以當你知道你會改變並傳遞它們時，最好避免分配，而是堅持完全複製它們（就像在「works」情況下所做的那樣）。

為了進一步閱讀，這是一個很好的資源：https://go.dev/blog/slices-簡介

以上是在Golang中使用回溯演算法時如何正確複製數組？的詳細內容。更多資訊請關注PHP中文網其他相關文章！