Comment copier correctement un tableau lors de l'utilisation de l'algorithme de backtracking dans Golang ?

Copier correctement le tableau est un problème important lors de l'utilisation de l'algorithme de backtracking dans Golang. Les algorithmes de backtracking nécessitent généralement des modifications du tableau pendant le processus récursif, mais nous devons parfois sauvegarder l'état du tableau d'origine afin de revenir à l'étape précédente. Dans ce cas, nous ne pouvons pas simplement affecter le tableau d'origine directement à une nouvelle variable car ils partagent le même espace mémoire et la modification d'un tableau affectera l'autre tableau. La solution à ce problème consiste à utiliser une copie complète, qui crée un nouveau tableau et copie les valeurs du tableau d'origine les unes après les autres dans le nouveau tableau. Dans Golang, cette opération peut être effectuée à l'aide de la fonction copy(), qui copie le contenu du tableau au niveau des octets pour garantir que le nouveau tableau est complètement indépendant du tableau d'origine. En copiant correctement le tableau, nous pouvons manipuler le tableau en toute sécurité dans l'algorithme de backtracking sans affecter l'état des données d'origine.

Contenu de la question

J'ai un tableau simple avec des valeurs [1, 2, 3] et je veux trouver toutes les permutations. Je ne comprends pas pourquoi la partie "copie" du code est déplacée avant que la boucle n'interrompe le programme.

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
}

Lorsque la copie est hors de la boucle, le résultat est le suivant : [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 3 3] [3 3 3]]

Lorsque la copie est dans une boucle, le résultat est le suivant : [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

Dans la première sortie, il y a deux tableaux avec [3,3,3] ce qui est faux

Solution

Vous avez dit 我既不修改“c”或“r”也不附加到它们, cette partie est correcte.

Dans la première itération de la boucle, Les tranches c 和 curr pointent vers différents tableaux de support, donc c'est très bien.

Mais quand tu le fais

curr = c

Plus tard, vous assignez les deux tranches pour qu'elles pointent vers le même tableau de support.

Cela signifie qu'à la deuxième itération, le tableau de sauvegarde de votre append 可以修改 curr 和 curr （“可以”，因为调整大小会更改 curr).

C'est ce qui provoque le comportement étrange que vous voyez ci-dessus.

Les tranches à emporter sont un peu délicates, donc lorsque vous savez que vous allez les modifier et les faire circuler, il est préférable d'éviter de les attribuer et de vous en tenir à les copier exactement (comme vous le faites dans le cas des "travaux").

Pour en savoir plus, voici une excellente ressource : https://go.dev/blog/slices-introduction

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!