均匀分布与天真的洗牌？

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 万次会产生非常接近均匀的分布。

以上就是均匀分布与天真的洗牌？的详细内容，更多请关注编程网其它相关文章！