La génération de la combinaison golang a fait une erreur

Question

Je suis confronté à un problème de programmation

Étant donné deux nombres entiers n et k, renvoyer toutes les combinaisons possibles de k nombres parmi 1 ... n.

et avec l'entrée n = 5, k = 4, la sortie devrait être [[1,2,3,4], [1,2,3,5], [1,2,4,5], [1,3,4,5], [2,3,4,5]], ce qui suit est ma solution golang

func combine(n int, k int) [][]int {
    result := [][]int{}
    comb := []int{}
    subcom(0, k, n, &comb, &result)
    return result
}

func subcom(s, k, n int, comb *[]int, result *[][]int) {
    if k > 0 {
        for i := s + 1; i <= n-k+1; i++ {
            c := append(*comb, i)
            subcom(i, k-1, n, &c, result)
        }
    } else {
        *result = append(*result, *comb)
    }
}

Je pense que ma solution est correcte, mais elle renvoie [[1 2 3 5] [1 2 3 5] [1 2 4 5] [1 3 4 5] [2 3 4 5]]].

Après débogage, j'ai constaté que [1 2 3 4] avait été ajouté à la tranche de résultat au début, mais qu'il avait ensuite été remplacé par [1 2 3 5], ce qui a entraîné la répétition de deux [1 2 3 5]. Mais je n'arrive pas à comprendre ce qui ne va pas ici.

Answer 1

Il s'agit d'une erreur courante lorsque l'on utilise append .

Quand votre code s'exécute c:=append(*comb,i) il essaie d'abord d'utiliser la mémoire allouée dans le tableau sous-jacent pour ajouter un nouvel élément et ne crée une nouvelle tranche que s'il n'y parvient pas. C'est ce qui modifie le [1 2 3 4] a [1 2 3 5] - car ils partagent la même mémoire sous-jacente.

Pour résoudre ce problème, copiez le moment où vous voulez ajouter le résultat :

now := make([]int,len(*comb))
copy(now,*comb)
*result = append(*result,now)

Ou utilisez un raccourci de la copie :

*result = append(*result, append([]int{},*comb...))

Mise à jour :

Pour comprendre ce que j'entends par mémoire sous-jacente, il faut comprendre le modèle interne de la tranche de Go.

En Go, une tranche possède une structure de données appelée SliceHeader qui est accessible par reflect et c'est ce à quoi il est fait référence lorsque vous utilisez la fonction unsafe.Sizeof et en prenant l'adresse.

En SliceHeader en prenant soin de trois éléments : Len , Cap et un Ptr . Les deux premiers sont triviaux : ils sont ce que len() y cap() est pour. Le dernier est un uintptr qui pointe vers la mémoire des données que la tranche contient.

Lorsque vous copiez une tranche de manière superficielle, un nouveau fichier SliceHeader est créé mais avec le même contenu, notamment Ptr . La mémoire sous-jacente n'est donc pas copiée, mais partagée.