java.util.随机真的那么随机吗？我怎么才能生成52！（阶乘）可能的序列？

Question

我一直在使用Random（java.util.Random）洗牌52张牌。有52个！（8.0658175e 67）可能性。然而，我发现java的种子。util。Random是一个长的，在2^64（1.8446744e 19）时要小得多。

从这里，我怀疑java.util.Random是否真的是随机的；它真的能够产生所有52个！可能性吗？

如果不是，我如何可靠地生成一个更好的随机序列，可以产生所有52个！可能性？

Answer 1

一般来说，如果52项列表的最大循环长度小于226位，伪随机数生成器（PRNG）无法从所有排列中进行选择。

java.util.Random实现了一个模数为2⁴⁸的算法，最大循环长度仅为48位，比我提到的226位少得多。您将需要使用另一个具有更大循环长度的PRNG，特别是最大循环长度为52阶乘或更大的PRNG。

另请参阅我关于随机数生成器的文章中的“洗牌”。

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

虽然java.security.SecureRandom允许传递无限长度的种子，但SecureRandom实现可以使用底层PRNG（例如，“SHA1PRNG”或“DRBG”）。它取决于PRNG的最大周期长度，是否能够从52种阶乘排列中进行选择。

Answer 2

你的分析是正确的：在一个伪随机数生成器中植入任何特定的种子，在洗牌后必须产生相同的序列，将你可以获得的排列数限制在2⁶⁴。这个断言很容易通过调用集合进行实验验证。洗牌两次，传递一个用相同种子初始化的随机对象，并观察两次随机洗牌是否相同。

因此，解决这个问题的一个办法是使用一个随机数生成器，允许产生更大的种子。Java提供了SecureRandom类，该类可以用几乎无限大小的byte[]数组初始化。然后可以将SecureRandom的实例传递给集合。洗牌完成任务：

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

Answer 3

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

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

您的方法的根本缺陷是，它试图使用64位熵（随机种子）在~2²²⁶可能性之间进行选择。为了在~2²²⁶种可能性之间做出公平的选择，你必须找到一种方法来产生226位的熵，而不是64位。

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

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

一旦你有了这226个随机位，剩下的就可以确定地完成，java的属性也是如此。util。随机的可以变得无关紧要。下面是方法。

假设我们总共生成了52个！排列（请耐心听我说）并按字典顺序进行排序。

要选择一个排列，我们只需要一个介于0和52之间的随机整数-1。这个整数就是我们的226位熵。我们将使用它作为排列排序列表的索引。如果随机指数是均匀分布的，你不仅可以保证所有的排列都可以被选择，而且它们都会被等概率地选择（这比问题所要求的更有力的保证）。

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

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

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]不要与主持人混淆。：）