java.util.Random真的那么随机吗？我该如何生成52！（部分）可能的顺序？

Question

我一直在Random (java.util.Random)洗牌52张牌。有52个！（8.0658175e +
67）的可能性。但是，我发现for的种子java.util.Random是a long，它的大小要小得多，为2 ^ 64（1.8446744e +
19）。

从这里开始，我怀疑是否java.util.Random 真的那么随机 ；实际上有能力生成全部52个！可能性？

如果没有，我如何可靠地生成可以产生全部52个更好的随机序列！可能性？

Answer 1

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

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

您的方法的根本缺陷在于，它试图使用64位熵（随机种子）在〜2 226种可能性之间进行选择。要在〜2
226种可能性之间进行合理选择，您将必须找到一种方法来生成226位（而不是64位）熵。

有几种产生随机位的方法：专用硬件，CPU指令，OS接口，在线服务。在您的问题中已经存在一个隐含的假设，即您可以某种方式生成64位，因此只需将您打算做的事情做四次，然后将多余的位捐赠给慈善机构即可。:)

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

一旦有了这226个随机位，其余的就可以确定地完成，因此 的属性java.util.Random可以变得无关紧要。这是怎么回事。

假设我们生成了全部52个！排列（与我同在）并按字典顺序对其进行排序。

要选择一种排列，我们需要的是0和之间的一个随机整数52!-1。这个整数是我们的226位熵。我们将其用作排列的排序列表的索引。如果随机索引是均匀分布的，不仅可以保证可以选择所有排列，还可以等
概率 选择 它们 （这比问题要强得多）。

现在，您实际上不需要生成所有这些排列。给定一个在我们假设的排序列表中随机选择的位置，您可以直接生产一个。可以使用Lehmer
[1]代码在O（n
2）时间内完成此操作（另请参见编号置换和阶乘数字系统）。这里的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]不要与Lehrer混淆。:)