java.util.Random真的是完全随机的吗？我如何生成52!（阶乘）个可能的序列？

Question

java.util.Random真的是完全随机的吗？我如何生成52!（阶乘）个可能的序列？

205

我一直使用Random (java.util.Random)来洗牌一副有52张牌的扑克牌。总共有52！(8.0658175e+67)种可能性。但是，我发现java.util.Random的种子是一个long，比较小，只有2^64 (1.8446744e+19)。

基于这个，我怀疑java.util.Random是否真的那么随机；它是否能够生成所有的52!种可能性？

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

- Sergei Emelianov

21

如何确保在52以上生成一个真正的随机数？Random 函数生成的数字并非真正的随机数，而是伪随机数。其中的 P 代表“伪”。如果需要真正的随机数，你需要使用随机数来源（例如 random.org）。 - T.J. Crowder

7

@JimGarrison，这不是OP要的。他说的是有10^68种可能的序列。由于每个伪随机序列都可由其种子标识，因此OP表示最多可能有2^64种不同的序列。 - Sergey Kalinichenko

6

我认为这是一个有趣的问题，值得思考。但是我不禁想知道你的问题背景：到底是什么要求你能够生成所有的52！个排列？例如，在现实世界的桥牌游戏中，我们可以洗牌并一次发一张牌，但由于许多不同的排列结果将导致相同的手牌，因此只有大约6e11种不同的手牌。换个方向想，你是否需要一个特别针对52！的解决方案，还是需要一个可以推广到两副牌混合在一起时的解决方案（104!/(2**52) 种可能性，或约2e150种）？ - NPE

9

以纸牌游戏“接龙”（Klondike）为例，52！恰好是可能手牌的数量。 - Sergey Emeliyanov

3

我认为这是一篇有趣的阅读：https://superuser.com/a/712583 - Dennis_E

显示剩余10条评论

9个回答

60

您的分析是正确的：使用特定种子初始化伪随机数生成器必须在洗牌后产生相同的序列，这将限制您可获得的排列数量为2⁶⁴。通过调用两次 Collection.shuffle 并传递一个使用相同种子初始化的 Random 对象，并观察两次随机洗牌的结果相同，可以通过实验轻松验证此断言。（点此查看实验）

解决方法是使用允许更大种子的随机数生成器。Java提供了SecureRandom类，该类可以使用虚拟无限大小的byte[]数组进行初始化。然后，您可以将SecureRandom实例传递给Collections.shuffle以完成任务：

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

- Sergey Kalinichenko

8

当然，一个大的种子并不能保证会产生所有的52!种可能性（这正是这个问题要探讨的）。作为一个思想实验，考虑一种病态的伪随机数生成器（PRNG），它采用任意大的种子并生成一个无限长的零序列。很明显，这个PRNG需要满足比仅使用足够大的种子更多的要求。 - NPE

2

@SerjArdovic 是的，根据Java文档，传递给SecureRandom对象的任何种子材料都必须是不可预测的。 - Sergey Kalinichenko

10

你说得对，尽管种子太小可以保证生成随机数的上限，但足够大的种子不能保证生成随机数的下限。这只是消除了理论上的上限，使 RNG 可以生成所有 52！种组合。 - Sergey Kalinichenko

5

@SerjArdovic 需要的最小字节数为29个（需要226位来表示52！可能的位组合，即28.25个字节，因此我们必须将其四舍五入）。请注意，使用29个字节的种子材料可以消除您可以获得的洗牌次数的理论上限，而不确定下限（请参见NPE有关采用非常大的种子并生成所有零序列的垃圾RNG的评论）。 - Sergey Kalinichenko

8

“SecureRandom”实现几乎一定会使用底层的伪随机数生成器。这取决于该伪随机数生成器的周期（以及在较小程度上，状态长度），它是否能够从52阶乘排列中选择。（请注意，文档表示“SecureRandom”实现“最少符合”某些统计测试，并生成“必须是加密强度”的输出，但对底层伪随机数生成器的状态长度或周期没有明确的下限要求。） - Peter O.

显示剩余7条评论

26

一般来说，如果伪随机数生成器（PRNG）的种子数量少于52的阶乘（例如，状态大小为225位或更少），它就无法从52个项目的列表中选择所有排列。这里并没有提到PRNG是否允许与排列数量相同或更多的种子，以及PRNG能否以相等的概率选择这些排列，而不是生成完全独立均匀随机整数的理想过程。

java.util.Random实现了一个模数为2的48次方的算法，并且最多允许那么多种子，远远少于52的阶乘。需要对一个52个项目的列表进行洗牌的应用程序最好避免使用种子数量少于52的阶乘的PRNG（尽管即使PRNG允许与52的阶乘数量相同或更多的种子，仅凭这一点还不足以确保PRNG能够以相等的概率从所有排列中选择）。

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

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

尽管java.security.SecureRandom允许传入几乎无限长度的种子，但SecureRandom的实现可以使用底层的伪随机数生成器（例如"SHA1PRNG"或"DRBG"）。而且，它取决于底层伪随机数生成器所允许的种子数量，是否能够从52的阶乘排列中进行选择，除非例如，该伪随机数生成器使用与应用程序不透明的独立随机性重新种子化。

- Peter O.

18

提前道歉，这可能有点难理解...

首先，您已经知道java.util.Random并不是完全随机的。它以完全可预测的方式从种子生成序列。您的观点是完全正确的，由于种子只有64位长，它只能生成2^64个不同的序列。如果您以某种方式生成了64位真正的随机数并使用它们来选择种子，您不能使用该种子随机地选择所有52!个可能的序列，使它们具有相等的概率。

然而，只要您不会实际生成超过2^64个序列，只要没有任何“ 特殊的”或“明显特殊的”2^64个序列，这个事实就 没有任何影响。

假设您有一个使用1000位种子的更好的伪随机数生成器（PRNG）。想象一下，您有两种方法来初始化它——一种方法将使用整个种子进行初始化，另一种方法将在初始化之前将种子哈希为64位。

如果您不知道哪个初始化程序是哪个，则可以编写任何测试来区分它们吗？除非您足够（不）幸运，以至于用相同的64位两次初始化不良程序，否则答案是否定的。您不能在没有对特定PRNG实现中某些弱点的详细了解的情况下区分两种初始化程序。

或者说，假设Random类有一个包含2^64个序列的数组，在很遥远的过去某个时刻完全随机地选择了这些序列，并且种子只是这个数组中的一个索引。

因此，实际上Random使用仅64位种子在统计上不一定成问题，只要不会有重复使用相同种子的显著机会。

当然，对于密码学目的而言，64位种子就不够用了，因为让系统两次使用相同的种子具有可行性。

编辑：

我应该补充说明，即使以上所有内容都是正确的，但实际上java.util.Random的实现并不太好。如果你正在编写一款扑克游戏，也许可以使用MessageDigest API生成"MyGameName"+System.currentTimeMillis()的SHA-256哈希值，并使用这些位来洗牌。根据上述论点，只要用户不是真正赌博，就不必担心currentTimeMillis返回长整型。如果你的用户确实在进行真正的赌博，那么请使用无种子的SecureRandom。

- Matt Timmermans

6

@ThorstenS，你如何编写任何一种测试来确定有些牌组合永远不可能出现？ - Matt Timmermans

2

有几个随机数测试套件可用，例如George Marsaglia的Diehard或Pierre L'Ecuyer / Richard Simard的TestU01，它们可以轻松地发现随机输出中的统计异常。对于牌检查，您可以使用两个方块。您确定卡片顺序。第一个方块显示前两张卡的位置作为xy对：第一张卡作为x和第二张卡相对于第一张卡的差异（！）位置（-26-25）作为y。第二个方块显示第三张和第四张卡，其相对于第二/第三张卡为(-25-25)。如果您运行它一段时间，这将立即显示您分布中的间隙和群集。 - Thorsten S.

4

好的，那不是你说你能写的测试，但也不适用。为什么你假设分布中存在间隙和聚集，这些测试会揭示出来呢？这将意味着“PRNG实现中的特定弱点”，正如我所提到的，并且与可能的种子数量毫无关系。这样的测试甚至不需要重新生成种子。我在开始时确实警告过这很难理解。 - Matt Timmermans

3

@ThorstenS. 那些测试套件绝对不能确定你的源代码是一个64位种子的加密安全伪随机数生成器 (PRNG) 还是真正的随机数生成器 (RNG)。毕竟，那些测试套件就是用来测试 PRNG 的。即使你知道正在使用的算法，一个好的 PRNG 也会使得在没有进行状态空间的暴力搜索的情况下确定状态变得不可行。 - Sneftel

1

@ThorstenS：在一个真实的纸牌堆中，绝大多数的组合都不会出现。只是你不知道哪些是。对于一个还算合格的伪随机数生成器（PRNG），如果你可以测试一个给定输出序列是否属于它的映像，那么这就是PRNG的缺陷。像52！这样的荒谬巨大状态/周期并不需要；128位应该足够了。 - R.. GitHub STOP HELPING ICE

显示剩余7条评论

11

我会采取不同的方法。你的假设是正确的 - 你的伪随机数生成器无法涵盖所有52!种可能性。

问题是：你的纸牌游戏规模有多大？

如果你正在制作一个简单的类似纸牌游戏？ 那么你绝对不需要所有52！种可能性。相反，你可以这样看待它：一个玩家将拥有18万亿个独特的游戏。即使考虑到“生日悖论”，他们也必须打数十亿手才能遇到第一个重复的游戏。

如果你正在进行蒙特卡罗模拟？ 那么你可能没事。你可能需要处理由于PRNG中的“P”而产生的人为因素，但你可能不会因为低种子空间而遇到问题（再次强调，你在寻找百万亿个独特的可能性）。另一方面，如果你要处理大量迭代次数，那么，是的，你的低种子空间可能成为决定因素。

如果你正在制作多人卡牌游戏，特别是涉及到赌金的话？ 那么你需要在谷歌上搜索一些关于在线扑克网站如何处理你所询问的同样问题的信息。因为虽然低种子空间问题对于普通玩家而言不是很明显，但如果它值得投入时间来利用，那么它是可以被利用的。（扑克网站都经历过一个阶段，他们的 PRNG 被 "黑客" 破解了，从暴露的牌中推算种子，让某个人可以看到所有其他玩家的底牌）。如果你处于这种情况，不要简单地找一个更好的 PRNG - 你需要像处理加密问题一样认真对待它。

- Kevin

9

这是与dasblinkenlight本质相同的简短解决方案：

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

您不需要担心内部状态。以下是长说明：

当您以这种方式创建SecureRandom实例时，它会访问特定于操作系统的真随机数生成器。这可能是一个熵池，其中包含随机位（例如，对于纳秒计时器，纳秒精度基本上是随机的），或者是内部硬件数字生成器。

这个输入（！）可能仍然包含杂散的痕迹，被馈入一个密码强度的哈希函数中，该函数会去除这些痕迹。这就是为什么使用这些CSPRNGs，而不是为了创建这些数字本身！SecureRandom有一个计数器，跟踪使用了多少位（getBytes()，getLong()等），并且在必要时重新填充SecureRandom的熵位。

简而言之：只需忘记异议，将SecureRandom用作真正的随机数生成器即可。

- Thorsten S.

4

如果您将数字视为位（或字节）数组，那么您可以使用此Stack Overflow问题中建议的（安全的）Random.nextBytes解决方案，然后将该数组映射到new BigInteger(byte[])。请注意保留HTML标签。

- IvanK

3

一个非常简单的算法是将SHA-256应用于从0开始递增的整数序列。(如果需要“获取不同的序列”，可以附加盐。) 如果我们假设SHA-256的输出在0到2^256 - 1之间“几乎等同于”均匀分布的整数，则对于此任务，我们有足够的熵。

要从SHA256的输出(表示为整数)中获得排列，只需将其模52、51、50…降低到这个伪代码中的模数即可:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]

- Artelius

1

我的经验研究结果表明，Java.Random并非完全真正的随机。如果你使用Random类的“nextGaussian()”方法自行尝试，并生成足够大的样本种群以获取介于-1和1之间的数字，则图表呈正态分布，即高斯模型。

芬兰政府拥有一家赌博书商，每天一年四季都有一次抽奖游戏，中奖表显示书商以正常分布的方式提供奖金。我的Java模拟进行了500万次抽奖，结果表明使用nextInt()方法进行数字抽取时，获奖情况与我所在的书商在每次抽奖中提供的奖金类型相同，均为正态分布。

我最好的选择是避免在每个结尾中选择3和7这些数字，因为它们很少出现在获胜结果中。通过在1-70之间的整数中避免选择3和7数字，在几次中全部选对五个数字。

芬兰彩票每周六晚上开奖，如果你在39个数字中选择12个数字进行系统投注，并避免选择3和7的值，也许你可以在优惠券中获得5或6个正确的选择。

芬兰彩票有1-40的数字可供选择，使用12号码系统需要4张优惠券才能覆盖所有数字。总费用为240欧元，在长期内对于普通赌徒来说太昂贵了，无法承受。即使您与其他客户分享可购买的优惠券，如果想获得利润，您仍需相当幸运。

- Jere_Sumell

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NPE · Accepted Answer

选择随机排列需要同时更多和更少的随机性，而不是你的问题所暗示的。让我解释一下。

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

你的方法的根本缺陷在于它试图使用64位的熵（随机种子）在 ~2^226 种可能性之间进行选择。为了公平地在 ~2^226 种可能性之间进行选择，你将不得不找到一种生成226位熵的方法，而不是64位。

有几种方法可以生成随机位：专用硬件, CPU指令, OS接口, 在线服务。在你的问题中已经有一个隐含的假设，即你可以以某种方式生成64位，所以只需按照原计划进行四次操作，并将多余的位数捐赠给慈善机构。 :)

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

一旦你拥有了这226个随机位，剩下的就可以确定性地完成，因此java.util.Random的属性可以被忽略。以下是如何实现的。

假设我们生成所有52!个排列（请耐心等待），并按字典顺序排序。

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

现在，您实际上不需要生成所有这些排列。您可以直接生成一个，给定其在我们假想的排序列表中随机选择的位置。这可以使用Lehmer^[1] code（也请参阅numbering permutations和factoriadic number system）在O(n²)时间内完成。这里的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混淆。 :)