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

问题

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

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

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


#1 热门回答(84 赞)

选择随机排列需要同时具有比问题所暗示的越来越少的随机性。让我解释。
坏消息:需要更多的随机性。
你的方法的根本缺陷是它试图使用64位熵(随机种子)在~2226种可能性之间做出选择。要在~2226之间进行公平的选择,你必须找到一种方法来生成226位熵而不是64位。

有几种方法可以生成随机位:dedicated hardware,CPU instructions,OS interfaces,online services。在你的问题中已经有一个隐含的假设,你可以以某种方式生成64位,所以只要做你想要做的事情,只做四次,并将多余的比特捐给慈善机构。 :)
好消息:需要更少的随机性。
一旦你有226个随机位,其余的可以确定性地完成,并且java.util.Random的属性可以变得无关紧要。这是怎么回事。

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

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

现在,你实际上不需要生成所有这些排列。鉴于其在我们的假设排序列表中随机选择的位置,你可以直接生成一个。这可以使用Lemer [1]代码在O(n2)时间内完成(也参见numbering permutationsfactoriadic number system)。这里的n是你的牌组的大小,即52。

这个StackOverflow answer中有一个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]不要与Lehrer混淆。 :)


#2 热门回答(47 赞)

你的分析是正确的:用任何特定种子播种伪随机数生成器必须在shuffle之后产生相同的序列,将你可以获得的排列数限制为264.这个断言是easy to verify experimentally,调用Collection.shuffletwice,传递用同一种子初始化的Random对象,并观察两个随机混洗是相同的。

因此,对此的解决方案是使用允许更大种子的随机数发生器。 Java提供了SecureRandom类,可以用byte[]几乎无限大小的阵列进行初始化。然后,你可以传递SecureRandomCollections.shuffle的实例来完成任务:

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

#3 热门回答(16 赞)

通常,伪随机数发生器(PRNG)如果其状态长度小于226位,则不能从52项列表的所有排列中进行选择。

java.util.Random实现模数为248的算法;因此它的状态长度只有48位,比我提到的226位小得多。你将需要使用具有更大状态长度的另一个PRNG - 特别是具有52阶乘或更大阶段的PRNG。

另请参阅myarticle on random number generators中的"从所有排列中选择"。

这种考虑与PRNG的性质无关;它同样适用于加密和非加密PRNG(当然,无论何时涉及信息安全,非加密PRNG都是不合适的)。

尽管java.security.SecureRandom允许传入无限长度的种子,但实现可以使用基础PRNG(例如,"SHA1PRNG"或"DRBG")。它取决于PRNG的时期(在较小程度上,状态长度)是否能够从52个因子排列中进行选择。 (注意,I define "state length"是"PRNG可以采取的最大种子大小来初始化其状态而不缩短或压缩该种子")。