我一直在使用Random (java.util.Random)来洗牌一副52张牌。有52个!(8.0658175 e + 67)的可能性。然而,我发现java.util.Random的种子很长,它要小得多,为2^64 (1.8446744e+19)。
从这里开始,我怀疑java.util.Random是否真的那么随机;它真的能产生全部52个吗?可能性?
如果不是,我如何可靠地生成一个更好的随机序列,可以产生所有52!可能性?
我一直在使用Random (java.util.Random)来洗牌一副52张牌。有52个!(8.0658175 e + 67)的可能性。然而,我发现java.util.Random的种子很长,它要小得多,为2^64 (1.8446744e+19)。
从这里开始,我怀疑java.util.Random是否真的那么随机;它真的能产生全部52个吗?可能性?
如果不是,我如何可靠地生成一个更好的随机序列,可以产生所有52!可能性?
当前回答
让我提前道歉,因为这有点难以理解……
首先,您已经知道java.util.Random根本不是完全随机的。它以完全可预测的方式从种子中生成序列。你是完全正确的,因为种子只有64位长,它只能生成2^64个不同的序列。如果你要以某种方式生成64个真实的随机比特,并使用它们来选择一颗种子,你不能使用该种子在所有52个种子中随机选择!概率相等的可能序列。
然而,只要你实际上不会生成超过2^64的序列,只要它所生成的2^64序列没有什么“特别”或“明显特别”的地方,这个事实就没有什么意义。
假设你有一个更好的使用1000位种子的PRNG。假设您有两种方法来初始化它——一种方法是使用整个种子初始化它,另一种方法是在初始化它之前将种子散列到64位。
如果你不知道哪个初始化式是哪个,你能写一些测试来区分它们吗?除非你足够幸运,最终用相同的64位初始化了坏的那个,那么答案是否定的。如果不详细了解特定PRNG实现中的一些弱点,就无法区分这两个初始化器。
或者,想象Random类有一个2^64个序列的数组,这些序列是在遥远的过去的某个时间完全随机选择的,而种子只是这个数组的一个索引。
所以从统计学上来说,《Random》只使用64位的种子并不一定是个问题,只要你不太可能两次使用相同的种子。
当然,出于加密目的,64位种子是不够的,因为让一个系统两次使用相同的种子在计算上是可行的。
编辑:
I should add that, even though all of the above is correct, that the actual implementation of java.util.Random is not awesome. If you are writing a card game, maybe use the MessageDigest API to generate the SHA-256 hash of "MyGameName"+System.currentTimeMillis(), and use those bits to shuffle the deck. By the above argument, as long as your users are not really gambling, you don't have to worry that currentTimeMillis returns a long. If your users are really gambling, then use SecureRandom with no seed.
其他回答
选择一个随机排列同时需要比你的问题所暗示的更多和更少的随机性。让我解释一下。
坏消息是:需要更多的随机性。
你的方法的根本缺陷在于,它试图使用64位熵(随机种子)在~2226种可能性之间进行选择。为了公平地在2226种可能性中进行选择,你必须找到一种方法来产生226位而不是64位的熵。
生成随机比特的方法有几种:专用硬件、CPU指令、操作系统接口、在线服务。在你的问题中已经有一个隐含的假设,你可以以某种方式生成64位,所以只要做你想做的,只做四次,并将多余的位捐给慈善机构。:)
好消息是:需要更少的随机性。
一旦你有了这226个随机位,剩下的就可以确定地完成了,因此java.util.Random的属性就变得无关紧要了。以下是如何做到的。
假设我们生成了全部52个!排列(请原谅我),并按字典顺序进行排序。
要选择一种排列,我们只需要一个0到52之间的随机整数!-1。这个整数就是226比特的熵。我们把它作为排序序列的索引。如果随机指数是均匀分布的,你不仅可以保证所有的排列都可以被选择,而且它们将被等概率地选择(这是一个比问题所要求的更强的保证)。
现在,你实际上不需要生成所有这些排列。你可以直接生成一个,给定它在我们假设的排序列表中随机选择的位置。这可以在O(n2)时间内完成,使用Lehmer[1]代码(也参见编号排列和阶乘数系统)。这里的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"))));
}
别和莱勒搞混了。:)
一个非常简单的算法是将SHA-256应用于从0开始递增的整数序列。(如果想要“获得不同的序列”,可以添加盐。)如果我们假设SHA-256的输出与0到2256 - 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]
一般来说,伪随机数生成器(PRNG)如果最大周期长度小于226位,则不能从52项列表的所有排列中进行选择。
random实现了一个算法,其模量为248,最大周期长度不超过248,因此远小于2226(对应于我提到的226位)。您将需要使用另一个周期长度更大的PRNG,特别是最大周期长度为52 !或更大的PRNG。
请参见我关于随机数生成器的文章中的“洗牌”。
这一考虑与PRNG的性质无关;它同样适用于密码学和非密码学的prng(当然,非密码学的prng在涉及信息安全时是不合适的)。
虽然java.security.SecureRandom允许传入无限长度的种子,但SecureRandom实现可以使用底层的PRNG(例如,“SHA1PRNG”或“DRBG”)。这取决于PRNG的最大周期长度它是否能够从52个阶乘排列中进行选择。
简单的解决方案,本质上是相同的dasblinkenlight:
// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();
Collections.shuffle(deck, random);
你不需要担心内部状态。解释原因:
当您以这种方式创建securerrandom实例时,它将访问特定于操作系统的实例 真正的随机数发生器。这是一个熵池,其中的值是 访问包含随机位(例如,对于纳秒计时器,纳秒 精度基本上是随机的)或内部硬件数字生成器。
此输入(!)可能仍然包含虚假的跟踪被送入 加密强哈希,删除这些跟踪。这就是使用这些csprng的原因,而不是为了自己创建这些数字!SecureRandom有一个计数器,用于跟踪使用了多少位(getBytes(), getLong()等),并在必要时用熵位重新填充SecureRandom。
简而言之:简单地忘记反对意见,使用securerrandom作为真正的随机数生成器。
让我提前道歉,因为这有点难以理解……
首先,您已经知道java.util.Random根本不是完全随机的。它以完全可预测的方式从种子中生成序列。你是完全正确的,因为种子只有64位长,它只能生成2^64个不同的序列。如果你要以某种方式生成64个真实的随机比特,并使用它们来选择一颗种子,你不能使用该种子在所有52个种子中随机选择!概率相等的可能序列。
然而,只要你实际上不会生成超过2^64的序列,只要它所生成的2^64序列没有什么“特别”或“明显特别”的地方,这个事实就没有什么意义。
假设你有一个更好的使用1000位种子的PRNG。假设您有两种方法来初始化它——一种方法是使用整个种子初始化它,另一种方法是在初始化它之前将种子散列到64位。
如果你不知道哪个初始化式是哪个,你能写一些测试来区分它们吗?除非你足够幸运,最终用相同的64位初始化了坏的那个,那么答案是否定的。如果不详细了解特定PRNG实现中的一些弱点,就无法区分这两个初始化器。
或者,想象Random类有一个2^64个序列的数组,这些序列是在遥远的过去的某个时间完全随机选择的,而种子只是这个数组的一个索引。
所以从统计学上来说,《Random》只使用64位的种子并不一定是个问题,只要你不太可能两次使用相同的种子。
当然,出于加密目的,64位种子是不够的,因为让一个系统两次使用相同的种子在计算上是可行的。
编辑:
I should add that, even though all of the above is correct, that the actual implementation of java.util.Random is not awesome. If you are writing a card game, maybe use the MessageDigest API to generate the SHA-256 hash of "MyGameName"+System.currentTimeMillis(), and use those bits to shuffle the deck. By the above argument, as long as your users are not really gambling, you don't have to worry that currentTimeMillis returns a long. If your users are really gambling, then use SecureRandom with no seed.