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

一般来说，伪随机数生成器(PRNG)如果最大周期长度小于226位，则不能从52项列表的所有排列中进行选择。

java.util.Random实现了一个算法，其模量为2⁴⁸，最大周期长度仅为48位，比我提到的226位要小得多。您将需要使用另一个周期长度更大的PRNG，特别是最大周期长度为52 !或更大的PRNG。

参见“洗牌”;在我的关于随机数生成器的文章。

这一考虑与PRNG的性质无关;它同样适用于密码学和非密码学的prng(当然，非密码学的prng在涉及信息安全时是不合适的)。

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

你的分析是正确的:在伪随机数生成器中播种任何特定的种子必须在洗牌后产生相同的序列，将你可以获得的排列数量限制为2⁶⁴。这个断言是易于实验验证，通过调用Collection.shuffle两次，传递一个用相同种子初始化的Random对象，并观察到两次随机洗牌是相同的。

因此，解决这个问题的方法是使用允许更大种子的随机数生成器。Java提供了SecureRandom类，它可以被初始化为几乎无限大小的byte[]数组。然后你可以将SecureRandom的一个实例传递给Collections.shuffle来完成任务:

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

如果你认为数字只是一个比特(或字节)数组，那么也许你可以使用这个堆栈溢出问题中建议的(Secure)Random.nextBytes解决方案，然后将数组映射到new BigInteger(byte[])。

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

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

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

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

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

一旦你有了这226个随机位，剩下的就可以确定地完成了，所以java.util.Random的属性可以变得无关紧要。以下是如何做到的。

假设我们生成了全部52个!排列(请原谅我)，并按字典顺序进行排序。

要从排列中选择一个，我们只需要在0和52!-1之间选择一个随机整数。这个整数就是226比特的熵。我们把它作为排序序列的索引。如果随机索引是均匀分布的，你不仅可以保证所有的排列都可以被选择，而且它们将被选择等概率的(这是一个比问题所要求的更强的保证)。

现在，你实际上不需要生成所有这些排列。你可以直接生成一个，给定它在我们假设的排序列表中随机选择的位置。这可以使用黄土<一口>[1]< /一口>代码(也参见编号排列和因数数系统)在O(n²)时间内完成。这里的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]不要和莱勒混淆。：）

让我提前道歉，因为这有点难以理解……

首先，你已经知道java.util.Random根本不是完全随机的。它以完全可预测的方式从种子中生成序列。你是完全正确的，因为种子只有64位长，它只能生成2^64个不同的序列。如果你要以某种方式生成64个真实随机位并使用它们来选择一个种子，你不能使用该种子在52!概率相等的可能序列。

然而，这个事实是无关紧要，只要你实际上不会生成超过2^64的序列，只要它可以生成的2^64序列没有任何“特殊”或“明显特殊”。

假设你有一个更好的使用1000位种子的PRNG。假设您有两种方法来初始化它——一种方法是使用整个种子初始化它，另一种方法是在初始化它之前将种子散列到64位。

如果你不知道哪个初始化式是哪个，你能写一些测试来区分它们吗?除非你(un)足够幸运，最终用相同 64位两次初始化坏的那个，那么答案是否定的。如果不详细了解特定PRNG实现中的一些弱点，就无法区分这两个初始化器。

或者，想象Random类有一个2^64个序列的数组，这些序列是在遥远的过去的某个时间完全随机选择的，而种子只是这个数组的一个索引。

因此，Random只使用64位种子的事实实际上是不在统计上必然是一个问题，只要你没有显著的机会使用相同的种子两次。

当然，对于加密的目的，64位种子是不够的，因为让一个系统两次使用相同的种子在计算上是可行的。

编辑:

我应该补充一点，即使上面所有的都是正确的，java.util.Random的实际实现并不棒。如果你正在编写一个纸牌游戏，可能会使用MessageDigest API来生成"MyGameName"+System.currentTimeMillis()的SHA-256哈希，并使用这些位来洗牌。根据上面的论点，只要你的用户不是真的在赌博，你就不必担心currentTimeMillis返回一个long。如果你的用户是真的在赌博，那么使用SecureRandom不带种子。

在这个问题上，我要采取一点不同的方法。你的假设是对的——你的PRNG不可能击中所有52个!的可能性。

问题是:你的纸牌游戏规模有多大?

如果你正在制作一款简单的克朗代克风格游戏?那么你绝对没有需要 52!的可能性。相反，可以这样看:一个玩家将有18个百万的三次方不同的游戏。即使考虑到“生日问题”，他们也必须在遇到第一个重复游戏之前玩数十亿手牌。

如果你在做蒙特卡罗模拟?那么你是可能好吧。您可能不得不处理由于PRNG中的“P”而产生的工件，但是您可能不会因为低种子空间而遇到问题(再次强调，您看到的是无数种独特的可能性)。另一方面，如果您正在处理大量的迭代计数，那么，是的，您的低种子空间可能是一个交易破坏者。

如果你正在制作一款多人卡牌游戏，特别是涉及到金钱的时候?然后你将需要做一些谷歌在线扑克网站如何处理相同的问题，你正在询问。因为对于普通玩家来说，低种子空间问题不是明显的，但如果值得投入时间的话，它就是可采。(所有的扑克网站都经历过一个阶段，他们的prng被“黑客”，让别人看到所有其他玩家的洞牌，只需要从暴露的牌中推断种子。)如果这是你所处的情况，不只是找到一个更好的PRNG -你需要像对待加密问题一样认真对待它。

简单的解决方案，本质上是相同的dasblinkenlight:

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


Collections.shuffle(deck, random);

你不需要担心内部状态。解释原因:

此输入(!)可能仍然包含虚假的跟踪被馈送到a 加密强哈希，删除这些跟踪。这就是使用这些csprng的原因，而不是为了自己创建这些数字!SecureRandom有一个计数器，跟踪使用了多少位(getBytes()， getLong()等)和必要时用熵位重新填充SecureRandom.

简而言之:简单地忘记反对并使用SecureRandom作为真正的随机数生成器。

一个非常简单的算法是将SHA-256应用于从0开始递增的整数序列。(如果想要“获得不同的序列”，可以添加盐。)如果我们假设SHA-256的输出与0到2²⁵⁶ - 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]

我的实证研究成果是Java。随机并不完全是随机的。如果您尝试使用随机类“nextGaussian()”方法，并为-1到1之间的数字生成足够大的样本总体，则图是正态分布域，即高斯模型。

芬兰政府拥有的赌博书签每天都有一次，全年每天都抽彩票，中奖表显示书签书签以正常分布的方式给予奖金。我的Java模拟500万次抽奖显示，与nextInt() - method使用数字抽奖，奖金正态分布与My Bookmarker在每次抽奖中处理奖金相同。

我最好的选择是避免在结尾的每一个数字中出现3和7，这是事实，它们很少有获胜的结果。有几次通过避免在整数1-70之间的一列中的3和7个数字，赢得了5个选择中的5个。

芬兰彩票每周周六晚上抽一次，如果你在39个数字中抽12个，也许你会避开3和7个数字，在优惠券中获得5或6个正确的选择。

芬兰彩票有数字1-40可供选择，它需要4张优惠券来覆盖所有的数字与12号系统。总花费是240欧元，从长远来看，对于经常赌博的人来说，这太贵了，不玩就会破产。即使你把优惠券分享给其他可以购买的客户，如果你想盈利，你也必须非常幸运。