我一直在使用 Random (java.util.Random)
来洗一副 52 张牌。有52个! (8.0658175e+67) 个可能性。然而,我发现 java.util.Random
的种子是一个 long
,在 2^64 (1.8446744e+19) 时要小得多。
从这里开始,我怀疑 java.util.Random
是否真的那么随机;它真的能够生成所有 52 个吗?可能性?
如果不是,我怎样才能可靠地生成一个可以产生全部 52 个的更好的随机序列!可能性?
最佳答案
与您的问题所暗示的相比,选择随机排列同时需要更多和更少的随机性。让我解释一下。
坏消息:需要更多随机性。
您的方法的根本缺陷是它试图使用 64 位熵(随机种子)在 ~2226 种可能性之间进行选择。要在 ~2226 种可能性之间进行公平选择,您必须找到一种方法来生成 226 位熵而不是 64 位。
有几种方法可以生成随机位:dedicated hardware、CPU instructions、OS interfaces、online services。您的问题中已经有一个隐含的假设,即您可以以某种方式生成 64 位,所以只要做您想做的任何事情,只做四次,然后将多余的位捐赠给慈善机构。 :)
好消息:需要更少的随机性。
一旦你有了这 226 个随机位,其余的就可以确定性地完成,所以 java.util.Random
的属性可以变得无关紧要。方法如下。
假设我们生成了全部 52 个!排列(请耐心等待)并按字典顺序对它们进行排序。
要选择一种排列,我们只需要一个介于 0
和 52!-1
之间的随机整数。该整数是我们的 226 位熵。我们将使用它作为排序排列列表的索引。如果随机索引是均匀分布的,那么您不仅可以保证所有排列都可以被选择,而且它们将被等概率地选择(这比问题所要求的更有保证)。
现在,您实际上不需要生成所有这些排列。您可以直接生成一个,因为它在我们假设的排序列表中是随机选择的。这可以使用 Lehmer[1] code 在 O(n2) 时间内完成(另见 numbering permutations 和 factoriadic number system )。这里的 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 混淆。 :)
关于java - java.util.Random 真的那么随机吗?我怎样才能生成52! (阶乘)可能的序列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51771206/