java.util.Random真的是随机的吗？我怎么能产生52!(阶乘)可能的序列？

Question

我一直Random (java.util.Random)用来洗牌一副52张牌.有52个!(8.0658175e + 67)可能性.然而,我发现种子java.util.Random是a long,它在2 ^ 64(1.8446744e + 19)处小得多.

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

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

Answer 1

选择随机排列同时需要的随机性比问题所暗示的要多.让我解释.

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

你的方法的根本缺陷是它试图使用64位熵(随机种子)在~2 ^226种可能性之间进行选择.要在~2 ^226种可能性之间进行公平选择,您将不得不找到一种方法来生成226位熵而不是64位.

有几种方法可以生成随机位:专用硬件,CPU指令,OS接口,在线服务.在你的问题中已经有一个隐含的假设,你可以以某种方式生成64位,所以只要你做任何事情,只做四次,并将多余的位捐赠给慈善机构.:)

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

一旦你有226个随机位,其余的可以确定性地完成,因此可以使属性java.util.Random无关紧要.这是怎么回事.

假设我们生成所有52个!排列(跟我一起)并按字典顺序排序.

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

现在,您实际上并不需要生成所有这些排列.鉴于其在我们的假设排序列表中随机选择的位置,您可以直接生成一个.这可以使用Lehmer ^[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]不要与Lehrer混淆.:)

Answer 2

您的分析是正确的:使用任何特定种子播种伪随机数生成器必须在重排后生成相同的序列,从而将您可以获得的排列数限制为2 ⁶⁴.通过调用两次,传递使用相同种子初始化的对象,并观察两个随机shuffle是相同的,这个断言很容易通过实验验证.Collection.shuffleRandom

因此,对此的解决方案是使用允许更大种子的随机数发生器.Java提供的SecureRandom类可以使用byte[]几乎无限大小的数组进行初始化.然后,您可以传递一个SecureRandomto 的实例Collections.shuffle来完成任务:

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

Answer 3

通常,伪随机数发生器(PRNG)如果其状态长度小于226位,则不能从52项列表的所有排列中进行选择.

java.util.Random实现模数为2 ⁴⁸的算法; 因此它的状态长度只有48位,远远小于我提到的226位.您将需要使用具有更大状态长度的另一个PRNG - 特别是具有52阶乘或更大阶段的PRNG.

另请参阅我的随机数生成器文章中的"随机播放 " .

这种考虑与PRNG的性质无关; 它同样适用于加密和非加密PRNG(当然,无论何时涉及信息安全,非加密PRNG都是不合适的).

虽然java.security.SecureRandom允许传入无限长度的种子,但是SecureRandom实现可以使用底层PRNG(例如,"SHA1PRNG"或"DRBG").它取决于PRNG的时期(在较小程度上,状态长度)是否能够从52个因子排列中进行选择.(请注意,我将"状态长度"定义为"PRNG可以在不缩短或压缩该种子的情况下初始化其状态所需的种子的最大大小").

Answer 4

让我先提前道歉,因为这有点难以理解......

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

然而,只要你实际上不会生成超过2 ^ 64个序列,这个事实就没有任何意义了,只要它没有任何关于它可以生成的2 ^ 64序列的"特殊"或"明显特殊"..

让我们说你有一个更好的PRNG使用1000位种子.想象一下,你有两种方法来初始化它 - 一种方法是使用整个种子初始化它,并且一种方法会在初始化之前将种子散列到64位.

如果您不知道哪个初始化程序是哪个,您是否可以编写任何类型的测试来区分它们？除非你(非)幸运地最终用相同的 64位两次初始化坏的,否则答案是否定的.如果没有对特定PRNG实现中的某些弱点的详细了解,则无法区分这两个初始化器.

或者,假设Random该类具有2 ^ 64个序列的数组,这些序列在遥远的过去的某个时间完全和随机选择,并且种子只是该数组的索引.

这样的事实,Random仅使用64位,它的种子其实并不一定是统计上的问题,只要有您将使用相同的种子两次没有显著的机会.

当然,出于加密目的,64位种子是不够的,因为让系统两次使用相同的种子在计算上是可行的.

编辑:

我应该补充一点,尽管以上所有都是正确的,但实际的实现java.util.Random并不令人敬畏.如果您正在编写纸牌游戏,可以使用MessageDigestAPI生成SHA-256哈希值"MyGameName"+System.currentTimeMillis(),并使用这些位来改组牌组.通过上述论证,只要您的用户不是真正的赌博,您就不必担心currentTimeMillis返回时间长.如果你的用户是真正的赌博,然后用SecureRandom无种子.

Answer 5

我将对此采取一些不同的方法.你的假设是正确的 - 你的PRNG无法击中所有52个!可能性.

问题是:你的纸牌游戏的规模是多少？

如果你正在制作一个简单的克朗代克式游戏？ 那你肯定不需要全部52!可能性.相反,看它是这样的:一个玩家将有18个百万的三次不同的游戏.即使考虑到"生日问题",他们也必须在进入第一个复制游戏之前玩数十亿手牌.

如果你正在进行蒙特卡罗模拟？ 然后你可能没问题.由于PRNG中的'P',你可能不得不处理工件问题,但是你可能不会因为种子空间不足而遇到问题(同样,你会看到几个独特的可能性).另一方面,如果你正在处理大的迭代计数,那么,是的,你的低种子空间可能是一个交易破坏者.

如果你正在制作多人纸牌游戏,特别是如果你有钱吗？ 然后你需要在谷歌上搜索在线扑克网站如何处理你所询问的同样问题.因为虽然低种子空间问题对于普通玩家来说并不明显,但如果它值得花时间投资则可以利用.(扑克网站都经历了一个阶段,他们的PRNG被'黑客攻击',让某人看到所有其他玩家的底牌,只需从暴露的牌中推断种子.)如果这是你所处的情况,请不要"T能找到更好的PRNG -你需要尽可能认真地把它当作一个加密问题.

Answer 6

简短的解决方案与dasblinkenlight基本相同:

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

Collections.shuffle(deck, random);

您无需担心内部状态.很长的解释原因:

以SecureRandom这种方式创建实例时,它会访问特定于操作系统的真随机数生成器.这是访问值的熵池,其包含随机位(例如,对于纳秒定时器,纳秒精度基本上是随机的)或内部硬件数发生器.

这个仍然包含伪跟踪的输入(!)被送入加密强哈希,删除那些痕迹.这就是使用CSPRNG的原因,而不是自己创建这些数字!在SecureRandom具有跟踪多少位被用于(一个计数器getBytes(),getLong()等),并重新充SecureRandom以熵比特必要时.

简而言之:简单地忘记异议并将其SecureRandom用作真正的随机数生成器.