Bagaimana untuk menyalin tatasusunan dengan betul apabila menggunakan algoritma penjejakan belakang di Golang?

Menyalin tatasusunan dengan betul ialah isu penting apabila menggunakan algoritma penjejakan belakang di Golang. Algoritma penjejakan ke belakang biasanya memerlukan pengubahsuaian pada tatasusunan semasa proses rekursif, tetapi kadangkala kita perlu menyimpan keadaan tatasusunan asal untuk mengundur ke langkah sebelumnya. Dalam kes ini, kita tidak boleh hanya menetapkan tatasusunan asal terus kepada pembolehubah baharu kerana ia berkongsi ruang memori yang sama dan mengubah suai satu tatasusunan akan menjejaskan tatasusunan yang lain. Penyelesaian kepada masalah ini adalah dengan menggunakan salinan dalam, yang mencipta tatasusunan baharu dan menyalin nilai tatasusunan asal ke dalam tatasusunan baharu satu demi satu. Di Golang, operasi ini boleh dicapai menggunakan fungsi copy(), yang menyalin kandungan tatasusunan pada tahap bait untuk memastikan tatasusunan baharu benar-benar bebas daripada tatasusunan asal. Dengan menyalin tatasusunan dengan betul, kami boleh memanipulasi tatasusunan dengan selamat dalam algoritma penjejakan ke belakang tanpa menjejaskan keadaan data asal.

Kandungan soalan

Saya mempunyai tatasusunan ringkas dengan nilai [1, 2, 3] dan saya ingin mencari semua pilih atur. Saya tidak faham mengapa bahagian "salinan" kod dialihkan sebelum gelung memecahkan 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
}

Apabila salinan berada di luar gelung, hasilnya adalah seperti berikut: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 3 3] [3 3 3]]

Apabila salinan berada di dalam gelung, hasilnya adalah seperti berikut: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

Dalam output pertama, terdapat dua tatasusunan dengan [3,3,3] yang salah

Penyelesaian

Anda berkata 我既不修改“c”或“r”也不附加到它们, bahagian ini betul.

Dalam lelaran pertama gelung, Kepingan c 和 curr menghala ke tatasusunan sandaran yang berbeza, jadi tidak mengapa.

Tetapi apabila anda melakukannya

curr = c

Kemudian, anda sebenarnya menetapkan kedua-dua kepingan untuk menghala ke tatasusunan sandaran yang sama.

Ini bermakna pada lelaran kedua, tatasusunan sokongan append 可以修改 curr 和 curr （“可以”，因为调整大小会更改 curr anda).

Inilah yang menyebabkan tingkah laku pelik yang anda lihat di atas.

Potongan dalam perjalanan agak rumit, jadi apabila anda tahu anda akan menukar dan menyebarkannya, sebaiknya elakkan memberikannya dan sebaliknya terus menyalinnya dengan tepat (seperti yang anda lakukan dalam kes "kerja").

Untuk bacaan lanjut, berikut adalah sumber yang bagus: https://go.dev/blog/slices-introduction

Atas ialah kandungan terperinci Bagaimana untuk menyalin tatasusunan dengan betul apabila menggunakan algoritma penjejakan belakang di Golang?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!