php小編小新將為大家揭秘”均勻分布與天真的洗牌”之間的關系。在計算機科學中，洗牌是一種重要的操作，常用于隨機化數據或集合。而均勻分布是指在一定范圍內的隨機數分布是平均的。那么，洗牌是否能保證均勻分布呢？答案并不簡單，讓我們一起來探討這個問題。
問題內容
我正在對一個 3 int 數組進行 600 萬次洗牌。我在地圖中記錄數組的每個排列。下面是使用 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)
}
}
登錄后復制
由于我正在進行簡單的洗牌，我的理解是它不應該不產生均勻分布的排列。但這就是我得到的：
[184 -6 10] : 1000074 [184 10 -6] : 1000764 [-6 10 184] : 1000766 [10 184 -6] : 998090 [-6 184 10] : 1000479 [10 -6 184] : 999827
登錄后復制
這表明 6 種可能的排列中的每一種都發生大約 100 萬次。為什么我得到的分布看起來是均勻的？
編輯：將代碼更改為僅種子一次。我現在得到：
[-6 184 10] : 999507 [184 -6 10] : 1000401 [10 -6 184] : 1002163 [10 184 -6] : 999236 [-6 10 184] : 999016 [184 10 -6] : 999677
登錄后復制
編輯2：感謝霍布斯，我意識到我犯了一個愚蠢的錯誤。我應該洗牌 a，而不是 arr。我現在得到：
[10 -6 184] : 1111056 [-6 10 184] : 888442 [184 -6 10] : 888576 [10 184 -6] : 1109896 [-6 184 10] : 1113148 [184 10 -6] : 888882
登錄后復制
解決方法
您對 arr 進行了超過 600 萬次洗牌，而沒有在兩次洗牌之間將其恢復到其原始狀態 – 換句話說，您的 600 萬次試驗并不是獨立的。盡管每次洗牌的排列分布不均勻，但將這些排列相互疊加 600 萬次會產生非常接近均勻的分布。
