Uniform distribution versus naive shuffling?

php editor Xiaoxin will reveal the relationship between "uniform distribution and naive shuffling". In computer science, shuffling is an important operation often used to randomize data or collections. Uniform distribution means that the random number distribution is average within a certain range. So, can shuffling ensure even distribution? The answer is not simple, so let’s explore this question together.

Question content

I am shuffling a 3 int array 6 million times. I record each permutation of the array in a map. Below is the code using 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)
    }

}

Since I'm doing a simple shuffle, my understanding is that it shouldn't not produce an evenly distributed permutation. But this is what I get:

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

This shows that each of the 6 possible permutations occurs approximately 1 million times. Why does the distribution I get look uniform?

EDIT: Changed code to only seed once. I now get:

[-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: Thanks to Hobbs, I realized I made a stupid mistake. I should have shuffled a, not arr. I now get:

[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

You shuffled arr over 6 million times without restoring it to its original state between shuffles - In other words, your 6 million trials are not independent. Although the permutations of each shuffle are unevenly distributed, stacking these permutations on top of each other 6 million times produces a distribution that is very close to uniform.

The above is the detailed content of Uniform distribution versus naive shuffling?. For more information, please follow other related articles on the PHP Chinese website!