java.util.Random真的那么随机吗?我怎么能生成52!(阶乘)可能的序列?

2022-08-31 06:11:30

我一直在用洗牌一副52张牌。有52个!(8.0658175e+67) 可能性。然而,我发现 的种子是 一个 ,它在 2^64 (1.8446744e+19) 处要小得多。Random (java.util.Random)java.util.Randomlong

从这里开始,我怀疑是否真的那么随机;它实际上能够生成所有52个!可能性?java.util.Random

如果没有,我怎么能可靠地生成一个更好的随机序列,可以产生所有52个!可能性?


答案 1

选择随机排列需要的随机性同时比您的问题所暗示的要多和少。让我解释一下。

坏消息:需要更多的随机性。

你的方法中的根本缺陷是,它试图使用64位熵(随机种子)在大约2 226种可能性之间进行选择。要在~2226种可能性之间公平地进行选择,你必须找到一种方法来生成226位熵而不是64位。

有几种方法可以生成随机位:专用硬件CPU指令操作系统接口在线服务。在你的问题中已经有一个隐含的假设,你可以以某种方式生成64位,所以只要做你要做的事情,只有四次,并将多余的位捐给慈善机构。:)

好消息是:需要更少的随机性。

一旦你有了这226个随机位,其余的就可以确定性地完成,因此java.util.Random的属性可以变得无关紧要。方法如下。

假设我们生成了所有 52 个!排列(忍受我)并按字典顺序对它们进行排序。

要选择其中一个排列,我们所需要的只是 和 之间的单个随机整数。这个整数是我们的 226 位熵。我们将它用作排序排列列表的索引。如果随机索引是均匀分布的,您不仅可以保证可以选择所有排列,还可以平等地选择它们(这比问题所问的更强保证)。052!-1

现在,您实际上不需要生成所有这些排列。您可以直接生成一个,因为它在我们的假设排序列表中随机选择的位置。这可以在O(n2)时间内使用Lehmer[1]代码完成(另请参阅编号排列阶乘数字系统)。这里的n是你的甲板的大小,即52。

StackOverflow 答案中有一个 C 实现。有几个整数变量会在 n=52 时溢出,但幸运的是,在 Java 中您可以使用 。其余的计算几乎可以按原样转录:java.math.BigInteger

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

[1] 不要与莱勒混淆。:)


答案 2

您的分析是正确的:使用任何特定种子为伪随机数生成器设定种子必须在随机分配后产生相同的序列,从而将获得的排列数限制为 264。通过调用两次,传递使用相同种子初始化的对象,并观察两个随机洗牌是否相同,可以很容易地通过实验验证此断言。Collection.shuffleRandom

因此,解决这个问题的方法是使用允许更大种子的随机数生成器。Java提供了SecureRandom类,可以使用几乎无限大小的数组进行初始化。然后,您可以将 一个实例传递给 来完成任务:byte[]SecureRandomCollections.shuffle

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

推荐