均匀分布与朴素洗牌?

huangapple go评论85阅读模式
英文:

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 (
	&quot;fmt&quot;
	&quot;math/rand&quot;
	&quot;time&quot;
)

func randRange(min, max int) int {
	return rand.Intn(max-min+1) + min
}

func NaiveShuffle(arr *[3]int) {
	for i := 0; i &lt; 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 &lt;= 6000000; i++ {
		a := arr
		NaiveShuffle(&amp;arr)
		m[a]++
	}

	for k, v := range m {
		fmt.Println(k, &quot;:&quot;, 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 &lt; 3; i++ {
		for j := 0; j &lt; 3; j++ {
			for k := 0; k &lt; 3; k++ {
				a := []string{&quot;a&quot;, &quot;b&quot;, &quot;c&quot;}
				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(&quot;%v\n&quot;, a)
			}
		}
	}
	fmt.Printf(&quot;%v\n&quot;, 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)..

huangapple
  • 本文由 发表于 2023年2月13日 09:17:31
  • 转载请务必保留本文链接:https://go.coder-hub.com/75431202.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定