时间戳

首页 > 解决方案 > 无偏随机数组洗牌

java - 无偏随机数组洗牌

问题描述

当我想从 [1...n] 中对数组“perm”中的数字数组进行洗牌时，我用 Java 写道：

int[] perm = new int[n];
for (int i = 0; i < n; i++) {
     perm[i] = i;
}

for (int i = 0; i < n; i++) {
    int new_place = (int) (Math.random()*n); // Exchange element with any random element.
    int temp = perm[new_place];
    perm[new_place] = perm[i];
    perm[i] = temp;
}

但是本书将随机化代码编写为（仅在 for 循环中进行了更改）：

for (int i = 0; i < n; i++) {
    int new_place = i + (int) (Math.random() * (n-i)); // Exchange element with a random element to its right.
    int temp = perm[new_place];
    perm[new_place] = perm[i];
    perm[i] = temp;
}

他们说，通过他们编写的代码，他们通过从尚未选择的牌中统一选择来确保洗牌是随机的。（与我的方法相反，我从所有卡片中选择）。（我相信这是他们写的Fisher-Yates算法的修改版本）。

我只想知道我的代码（上面的代码）对于随机数生成是否也无偏见？如果是，为什么？如果不是，为什么？

（前 2 条评论是针对我问我所做的是否适合随机数生成的问题，但我想问它是否公正。但我当时不知道这个术语，抱歉。对于这个当前问题，第4条评论有一个很好的理解链接）。

标签： javaarraysshufflefisher-yates-shuffle

解决方案

您的代码似乎对生成的数组的分布存在偏差。6000 次统计结果n = 3如下。

static int[] shuffle(int n) {
    int[] perm = IntStream.range(0, n).toArray();
    for (int i = 0; i < n; i++) {
        int new_place = (int) (Math.random()*n);
        int temp = perm[new_place];
        perm[new_place] = perm[i];
        perm[i] = temp;
    }
    return perm;
}

public static void main(String[] args) {
    Map<int[], Integer> counts = new TreeMap<>(Arrays::compare);
    int n = 3;
    for (int i = 0; i < 6000; ++i)
        counts.compute(shuffle(n), (k, v) -> v == null ? 1 : v + 1);
    counts.entrySet()
        .forEach(e -> System.out.println(
            Arrays.toString(e.getKey()) + "=" + e.getValue()));
}

输出：

[0, 1, 2]=865
[0, 2, 1]=1113
[1, 0, 2]=1161
[1, 2, 0]=1093
[2, 0, 1]=873
[2, 1, 0]=895

[0, 1, 2]并且[2, 1, 0]似乎很少见。

用书上的代码执行时，变成如下。

static int[] shuffle(int n) {
    int[] perm = IntStream.range(0, n).toArray();
    for (int i = 0; i < n; i++) {
        int new_place = i + (int) (Math.random() * (n-i));
        int temp = perm[new_place];
        perm[new_place] = perm[i];
        perm[i] = temp;
    }
    return perm;
}

输出：

[0, 1, 2]=987
[0, 2, 1]=978
[1, 0, 2]=1014
[1, 2, 0]=994
[2, 0, 1]=1041
[2, 1, 0]=986

我无法解释为什么会这样，但你应该尝试一下。

推荐阅读