Distribution uniforme ou brassage naïf ?

L'éditeur PHP Xiaoxin révélera la relation entre "distribution uniforme et brassage naïf". En informatique, la lecture aléatoire est une opération importante souvent utilisée pour randomiser des données ou des collections. Une distribution uniforme signifie que la distribution des nombres aléatoires est moyenne dans une certaine plage. Alors, le brassage peut-il assurer une distribution uniforme ? La réponse n’est pas simple, alors explorons cette question ensemble.

Contenu de la question

Je mélange un tableau de 3 entiers 6 millions de fois. J'enregistre chaque permutation du tableau dans une carte. Vous trouverez ci-dessous le code utilisant go.

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func randrange(min, max int) int {
    return rand.intn(max-min+1) + min
}

func naiveshuffle(arr *[3]int) {
    for i := 0; i < 3; i++ {
        e := randrange(0, 2)
        arr[e], arr[i] = arr[i], arr[e]
    }
}

func main() {
    rand.seed(time.now().unixnano())
    m := make(map[[3]int]int, 6)
    arr := [3]int{-6,10,184}

    for i := 1; i <= 6000000; i++ {
        a := arr
        naiveshuffle(&arr)
        m[a]++
    }

    for k, v := range m {
        fmt.println(k, ":", v)
    }

}

Puisque je fais un simple mélange, je crois comprendre qu'il ne devrait pas pas produire une permutation uniformément répartie. Mais voici ce que j'ai obtenu :

[184 -6 10] : 1000074
[184 10 -6] : 1000764
[-6 10 184] : 1000766
[10 184 -6] : 998090
[-6 184 10] : 1000479
[10 -6 184] : 999827

Cela montre que chacune des 6 permutations possibles se produit environ 1 million de fois. Pourquoi la distribution que je reçois semble-t-elle uniforme ?

EDIT : code modifié pour ne lancer qu'une seule fois. J'obtiens maintenant :

[-6 184 10] : 999507
[184 -6 10] : 1000401
[10 -6 184] : 1002163
[10 184 -6] : 999236
[-6 10 184] : 999016
[184 10 -6] : 999677

Edit 2 : Grâce à Hobbs, j'ai réalisé que j'avais fait une erreur stupide. Je devrais mélanger a，而不是 arr. J'obtiens maintenant :

[10 -6 184] : 1111056
[-6 10 184] : 888442
[184 -6 10] : 888576
[10 184 -6] : 1109896
[-6 184 10] : 1113148
[184 10 -6] : 888882

Solution de contournement

Vous avez mélangé arr plus de 6 millions de fois sans le restaurer à son état d'origine entre les mélanges - en d'autres termes, vos 6 millions d'essais n'étaient pas indépendants du . Bien que les permutations de chaque mélange soient inégalement réparties, empiler ces permutations les unes sur les autres 6 millions de fois produit une distribution très proche de l'uniforme.

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!