Gleichverteilung versus naives Mischen?

PHP-Redakteur Xiaoxin wird den Zusammenhang zwischen „gleichmäßiger Verteilung und naivem Mischen“ aufdecken. In der Informatik ist das Mischen eine wichtige Operation, die häufig zum Randomisieren von Daten oder Sammlungen verwendet wird. Gleichverteilung bedeutet, dass die Zufallszahlenverteilung innerhalb eines bestimmten Bereichs durchschnittlich ist. Kann das Mischen also eine gleichmäßige Verteilung gewährleisten? Die Antwort ist nicht einfach, also lassen Sie uns diese Frage gemeinsam untersuchen.

Frageninhalt

Ich mische ein 3-Int-Array 6 Millionen Mal. Ich zeichne jede Permutation des Arrays in einer Karte auf. Unten ist der Code mit 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)
    }

}

Da ich ein einfaches Mischen durchführe, verstehe ich, dass es nicht nicht zu einer gleichmäßig verteilten Permutation kommen sollte. Aber das habe ich bekommen:

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

Dies zeigt, dass jede der 6 möglichen Permutationen ungefähr 1 Million Mal vorkommt. Warum sieht die Verteilung, die ich erhalte, einheitlich aus?

BEARBEITEN: Code so geändert, dass nur einmal gesät wird. Ich bekomme jetzt:

[-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: Dank Hobbs wurde mir klar, dass ich einen dummen Fehler gemacht hatte. Ich sollte mischen a，而不是 arr. Ich bekomme jetzt:

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

Workaround

Sie haben arr mehr als 6 Millionen Mal gemischt, ohne es zwischen den Mischvorgängen in seinen ursprünglichen Zustand zurückzusetzen – mit anderen Worten, Ihre 6 Millionen Versuche waren nicht unabhängig. Die . Obwohl die Permutationen jedes Mischvorgangs ungleichmäßig verteilt sind, führt das 6-Millionen-fache Stapeln dieser Permutationen übereinander zu einer Verteilung, die nahezu gleichmäßig ist.

Das obige ist der detaillierte Inhalt vonGleichverteilung versus naives Mischen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!