mélange de tableaux en Go

Question

J'ai essayé de traduire le code Python suivant en Go

import random

list = [i for i in range(1, 25)]
random.shuffle(list)
print(list)

mais j'ai trouvé ma version Go longue et maladroite car il n'y a pas de fonction de brassage et j'ai dû implémenter des interfaces et convertir des types.

Quelle serait une version Go idiomatique de mon code ?

Answer 1

La réponse de dystroy est parfaitement raisonnable, mais il est également possible de mélanger sans allouer de tranches supplémentaires.

for i := range slice {
    j := rand.Intn(i + 1)
    slice[i], slice[j] = slice[j], slice[i]
}

Véase cet article de Wikipedia pour plus de détails sur l'algorithme. rand.Perm utilise également cet algorithme en interne.

Answer 2

Comme votre liste n'est constituée que d'entiers de 1 à 25, vous pouvez utiliser Perm :

list := rand.Perm(25)
for i, _ := range list {
    list[i]++
}

Notez qu'en utilisant une permutation donnée par rand.Perm est un moyen efficace de mélanger n'importe quel tableau.

dest := make([]int, len(src))
perm := rand.Perm(len(src))
for i, v := range perm {
    dest[v] = src[i]
}

Answer 3

Depuis la version 1.10, Go inclut une version officielle de Le remaniement Fisher-Yates fonction.

Documentation : pkg/math/rand/#Shuffle

math/rand : ajouter Shuffle

Shuffle utilise l'algorithme de Fisher-Yates.

Puisqu'il s'agit d'une nouvelle API, elle nous donne l'occasion de d'utiliser une Int31n qui évite la plupart du temps la division.

En conséquence, BenchmarkPerm30ViaShuffle est environ 30 % plus rapide que BenchmarkPerm30 , bien que nécessitant une boucle d'initialisation séparée et en utilisant des appels de fonction pour échanger des éléments.

Voir aussi l'original CL 51891

Premièrement, comme a commenté por shelll :

N'oubliez pas d'ensemencer le hasard, sinon vous obtiendrez toujours le même ordre.
Par exemple rand.Seed(time.Now().UnixNano())

Exemple :

words := strings.Fields("ink runs from the corners of my mouth")
rand.Shuffle(len(words), func(i, j int) {
    words[i], words[j] = words[j], words[i]
})
fmt.Println(words)

Answer 4

Réponse de Evan Shaw a un bug mineur. Si nous itérons à travers la tranche de l'indice le plus bas vers le plus haut, pour obtenir un mélange uniformément (pseudo) aléatoire, selon la méthode du même article nous devons choisir un entier aléatoire dans l'intervalle [i,n) à l'opposé de [0,n+1) .

Cette implémentation fera ce dont vous avez besoin pour les grandes entrées, mais pour les petites tranches, elle effectuera un brassage non uniforme.

Pour utiliser rand.Intn() Nous pouvons le faire :

    for i := len(slice) - 1; i > 0; i-- {
        j := rand.Intn(i + 1)
        slice[i], slice[j] = slice[j], slice[i]
    }

en suivant le même algorithme de l'article de Wikipedia.

Answer 5

Vous pouvez peut-être aussi utiliser la fonction suivante :

func main() {
   slice := []int{10, 12, 14, 16, 18, 20}
   Shuffle(slice)
   fmt.Println(slice)
}

func Shuffle(slice []int) {
   r := rand.New(rand.NewSource(time.Now().Unix()))
   for n := len(slice); n > 0; n-- {
      randIndex := r.Intn(n)
      slice[n-1], slice[randIndex] = slice[randIndex], slice[n-1]
   }
}