英文:
even distribution with naive shuffle?
问题
我正在洗牌一个包含3个整数的数组,重复进行600万次。我使用Go语言将每个数组的排列计数保存在一个映射中。以下是使用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
这显示了每个可能的排列出现了大约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:感谢hobbs的指正,我意识到我犯了一个愚蠢的错误。我应该洗牌的是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
英文:
I'm shuffling an array of 3 int, 6 millions times. I keep count of each permutation of the array in a map. Code is below 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 naive shuffle my understanding is it should not produce an even distribution of permutations. 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 each of the 6 possible permutations occurs about ~1M times. Why do I get what appears to be an even distribution ?
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
EDIT2: Thanks to hobbs, I realized I made a silly mistake. I should shuffle 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
答案1
得分: 1
你在不恢复arr
到原始状态的情况下,反复洗牌arr
六百万次,换句话说,你的六百万次试验不是独立的。尽管每次洗牌的排列分布不均匀,但将这些排列叠加六百万次后,得到的分布非常接近均匀分布。
英文:
You're shuffling arr
over and over six million times without restoring it to its original state in between shuffles — in other words, your six million trials aren't independent. Even though each shuffle has an uneven distribution of permutations, composing those permutations on top of each other six million times results in a distribution that's quite close to uniform.
答案2
得分: 0
即使你将其恢复到原始状态,它也不是一个随机事件:
让我们列举所有情况:
m := map[string]int{}
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
for k := 0; k < 3; k++ {
a := []string{"a", "b", "c"}
a[i], a[0] = a[0], a[i]
a[j], a[1] = a[1], a[j]
a[k], a[2] = a[2], a[k]
m[a[0]+a[1]+a[2]]++
fmt.Printf("%v\n", a)
}
}
}
fmt.Printf("%v\n", m)
结果:
map[abc:4 acb:5 bac:5 bca:5 cab:4 cba:4]
它有所有的 3*3*3
= 27 种情况
但只有 C(3,1) = 6 种结果
它们必定不相等(4:5)。
英文:
Even you restoring it to its original state. its not a random event:
let us list all cases:
m := map[string]int{}
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
for k := 0; k < 3; k++ {
a := []string{"a", "b", "c"}
a[i], a[0] = a[0], a[i]
a[j], a[1] = a[1], a[j]
a[k], a[2] = a[2], a[k]
m[a[0]+a[1]+a[2]]++
fmt.Printf("%v\n", a)
}
}
}
fmt.Printf("%v\n", m)
result:
map[abc:4 acb:5 bac:5 bca:5 cab:4 cba:4]
it have all 3*3*3
= 27 cases
but only have C(3,1) = 6 result
it must be not equal(4:5)..
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论