java.util.Random真的是随机的吗？我怎么能产生52！ （阶乘）可能的序列？ [英] Is java.util.Random really that random? How can I generate 52! (factorial) possible sequences?

问题描述

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

I've been using Random (java.util.Random) to shuffle a deck of 52 cards. There are 52! (8.0658175e+67) possibilities. Yet, I've found out that the seed for java.util.Random is a long, which is much smaller at 2^64 (1.8446744e+19).

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

From here, I'm suspicious whether java.util.Random is really that random; is it actually capable of generating all 52! possibilities?

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

If not, how can I reliably generate a better random sequence that can produce all 52! possibilities?

推荐答案

选择随机排列需要的时间比你的问题所暗示的要多得多。让我解释一下。

Selecting a random permutation requires simultaneously more and less randomness than what your question implies. Let me explain.

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

你的方法的基本缺陷是它试图使用64位熵（随机种子）在~2 ²²⁶ 可能性之间做出选择。要在~2 ²²⁶ 之间做出相当的选择，你将不得不找到一种方法来生成226位熵而不是64位。

The fundamental flaw in your approach is that it's trying to choose between ~2²²⁶ possibilities using 64 bits of entropy (the random seed). To fairly choose between ~2²²⁶ possibilities you're going to have to find a way to generate 226 bits of entropy instead of 64.

有几种方法可以生成随机位：专用硬件， CPU指令， OS界面，在线服务。在你的问题中已经有一个隐含的假设，你可以以某种方式生成64位，所以只做你想做的事情，只做四次，并将多余的比特捐给慈善机构。 ：）

There are several ways to generate random bits: dedicated hardware, CPU instructions, OS interfaces, online services. There is already an implicit assumption in your question that you can somehow generate 64 bits, so just do whatever you were going to do, only four times, and donate the excess bits to charity. :)

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

一旦你有了那些226个随机位，其余的可以确定性地完成，因此 java.util.Random 的属性可以变得无关紧要。这是如何。

Once you have those 226 random bits, the rest can be done deterministically and so the properties of java.util.Random can be made irrelevant. Here is how.

假设我们生成所有52个！排列（跟我一起）并按字典顺序对它们进行排序。

Let's say we generate all 52! permutations (bear with me) and sort them lexicographically.

要选择其中一个排列，我们需要的是 0之间的单个随机整数和 52！-1 。那个整数是我们的226位熵。我们将它用作我们排序的排列列表的索引。如果随机索引是均匀分布的，不仅可以保证所有排列都可以选择，它们将被选择 equiprobably （这比问题所提出的更有保证）。

To choose one of the permutations all we need is a single random integer between 0 and 52!-1. That integer is our 226 bits of entropy. We'll use it as an index into our sorted list of permutations. If the random index is uniformly distributed, not only are you guaranteed that all permutations can be chosen, they will be chosen equiprobably (which is a stronger guarantee than what the question is asking).

现在，您实际上并不需要生成所有这些排列。鉴于其在我们的假设排序列表中随机选择的位置，您可以直接生成一个。这可以在O（n ² ）时间内使用 Lehmer ^{[ 1]} 代码（另见编号排列和 factoriadic number system ）。这里的n是你的套牌的大小，即52。

Now, you don't actually need to generate all those permutations. You can produce one directly, given its randomly chosen position in our hypothetical sorted list. This can be done in O(n²) time using the Lehmer^[1] code (also see numbering permutations and factoriadic number system). The n here is the size of your deck, i.e. 52.

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

There is a C implementation in this StackOverflow answer. There are several integer variables there that would overflow for n=52, but luckily in Java you can use java.math.BigInteger. The rest of the computations can be transcribed almost as-is:

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] 不要与<混淆a href =https://www.youtube.com/watch?v=gXlfXirQF3A\"rel =noreferrer> Lehrer 。 ：）

这篇关于java.util.Random真的是随机的吗？我怎么能产生52！ （阶乘）可能的序列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！