Wie kopiere ich ein Array korrekt, wenn ich den Backtracking-Algorithmus in Golang verwende?

Das korrekte Kopieren des Arrays ist ein wichtiges Thema bei der Verwendung des Backtracking-Algorithmus in Golang. Backtracking-Algorithmen erfordern normalerweise Änderungen am Array während des rekursiven Prozesses, aber manchmal müssen wir den Zustand des ursprünglichen Arrays speichern, um zum vorherigen Schritt zurückzukehren. In diesem Fall können wir das ursprüngliche Array nicht einfach direkt einer neuen Variablen zuweisen, da sie sich denselben Speicherplatz teilen und die Änderung eines Arrays Auswirkungen auf das andere Array hat. Die Lösung für dieses Problem besteht darin, eine tiefe Kopie zu verwenden, die ein neues Array erstellt und die Werte des ursprünglichen Arrays nacheinander in das neue Array kopiert. In Golang kann dieser Vorgang mit der Funktion copy() durchgeführt werden, die den Inhalt des Arrays auf Byte-Ebene kopiert, um sicherzustellen, dass das neue Array völlig unabhängig vom ursprünglichen Array ist. Durch korrektes Kopieren des Arrays können wir das Array im Backtracking-Algorithmus sicher manipulieren, ohne den Zustand der Originaldaten zu beeinträchtigen.

Frageninhalt

Ich habe ein einfaches Array mit den Werten [1, 2, 3] und möchte alle Permutationen finden. Ich verstehe nicht, warum der „Kopieren“-Teil des Codes verschoben wird, bevor die Schleife das Programm unterbricht.

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
}

Wenn sich die Kopie außerhalb der Schleife befindet, ist das Ergebnis wie folgt: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 3 3] [3 3 3]]

Wenn sich die Kopie in einer Schleife befindet, ist das Ergebnis wie folgt: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

In der ersten Ausgabe gibt es zwei Arrays mit [3,3,3], was falsch ist

Lösung

Sie sagten 我既不修改“c”或“r”也不附加到它们, dieser Teil ist richtig.

In der ersten Iteration der Schleife Slices c 和 curr verweisen auf verschiedene Backing-Arrays, das ist also in Ordnung.

Aber wenn du es tust

curr = c

Später weisen Sie beide Slices tatsächlich so zu, dass sie auf dasselbe Backing-Array verweisen.

Das bedeutet, dass bei der zweiten Iteration Ihr append 可以修改 curr 和 curr （“可以”，因为调整大小会更改 curr das Backing-Array verwendet.

Dies ist die Ursache für das seltsame Verhalten, das Sie oben sehen.

Slices in Go sind etwas knifflig. Wenn Sie also wissen, dass Sie sie ändern und weitergeben werden, vermeiden Sie am besten die Zuweisung und bleiben Sie stattdessen beim genauen Kopieren (wie Sie es im Fall „funktioniert“) tun.

Für weitere Lektüre gibt es hier eine tolle Ressource: https://go.dev/blog/slices-introduction

Das obige ist der detaillierte Inhalt vonWie kopiere ich ein Array korrekt, wenn ich den Backtracking-Algorithmus in Golang verwende?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!