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

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

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

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

有几种方法可以生成随机位: dedicated hardware , CPU instructions , OS interfaces , online services . 在你的问题中已经有一个隐含的假设,你可以以某种方式产生64位,所以只要做你打算做的任何事,只做4次,然后把多余的部分捐给慈善机构。:)

好消息是:减少随机性。

一旦你有了226个随机位,剩下的就可以确定地完成,所以 的性质 java.util.Random 会变得无关紧要 . 这就是方法。

假设我们生成所有52个!排列(忍受我)并排序字典。

要选择一个排列,我们只需要一个随机整数 0 和 52!-1 . 这个整数是我们的226位熵。我们将使用它作为排序排列列表的索引。如果随机索引是均匀分布的,那么不仅可以保证所有的排列都可以被选择,而且可以被选择 均衡 (这是比问题本身更有力的保证)。

现在,实际上不需要生成所有这些排列。考虑到它在我们假设的排序列表中随机选择的位置,您可以直接生成一个。这可以在O(n)中完成 ^2个 )使用时间 Lehmer ^[1] code (另见 numbering permutations 和 factoriadic number system ). 这里的n是你甲板的尺寸,即52。

这里有一个C实现 StackOverflow answer . 有几个整数变量会溢出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"))));
}

^[一] 不可混淆 Lehrer . :)

您的分析是正确的:在伪随机数生成器中植入任何特定的种子在洗牌后必须产生相同的序列,从而将可以获得的排列数限制为2 ^64个 . 这个断言是 easy to verify experimentally 通过打电话 Collection.shuffle 两次,通过 Random 对象初始化为同一种子,并观察两个随机洗牌是否相同。

解决这个问题的方法是使用一个随机数生成器,它允许一个更大的种子。Java提供 SecureRandom 可以用初始化的类 byte[] 几乎无限大小的数组。你可以通过一个 安全随机 到 Collections.shuffle 要完成任务:

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

一般来说,如果伪随机数发生器(PRNG)的状态长度小于226位,则它不能从52项列表的所有置换中进行选择。

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

另请参见我的 article on random number generators .

这种考虑独立于PRNG的性质;它同样适用于密码和非密码PRNG(当然,当涉及信息安全时,非密码PRNG是不合适的)。

尽管 java.security.SecureRandom 允许无限长的种子传入 SecureRandom 实现可以使用底层PRNG(例如,“SHA1PRNG”或“DRBG”)。它取决于PRNG的周期(在较小程度上,状态长度)是否能够从52个阶乘置换中进行选择。(注意 I define "state length" 作为种子的最大大小,PRNG可以用来初始化它的状态。 没有缩短或压缩种子 ").

让我提前道歉,因为这有点难理解。。。

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

然而,事实是 无足轻重 只要你不会生成超过2^64个序列,只要2^64个序列没有“特别的”或“明显的特别的” 可以 生成。

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

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

或者,想象一下 Random 类有一个由2^64个序列组成的数组,这些序列在很久以前的某个时间被完全随机地选择,而种子只是这个数组的索引。

所以事实上 随机的 它的种子实际上只使用64位 不 从统计学上来说,这一定是个问题,只要你不太可能使用同一个种子两次。

当然,为了 密码学 目的是,64位种子是不够的,因为让系统使用同一种子两次在计算上是可行的。

编辑:

我要补充的是,尽管上面的所有内容都是正确的,但是 java.util.Random 并不可怕。如果你在写纸牌游戏,可以用 MessageDigest 生成SHA-256散列的API "MyGameName"+System.currentTimeMillis() ,并使用这些位来洗牌。根据上面的论证,只要你的用户不是真的在赌博,你就不必担心 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);

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

当您创建 SecureRandom 通过这种方式,它访问特定于操作系统的 真随机数生成器。这要么是一个熵池,其中的值是 包含随机位的访问(例如,对于纳秒计时器,纳秒 精度基本上是随机的)或者是一个内部硬件编号生成器。

此输入(!)可能还含有虚假的痕迹 加密强哈希,用于删除这些跟踪。这就是使用这些csprng的原因,而不是创建这些数字本身!这个 安全随机 有一个计数器,跟踪使用了多少位( getBytes() , getLong() 等)和 重新加注 安全随机 必要时使用熵位 .

简而言之:简单地忘记反对和使用 安全随机 作为真随机数发生器。

如果您认为这个数字只是一个位(或字节)数组,那么您可以使用(Secure) Random.nextBytes 建议的解决方案 Stack Overflow 提问,然后将数组映射到 new BigInteger(byte[]) .

一个非常简单的算法是将SHA-256应用于从0向上递增的整数序列。(如果希望“获得不同的序列”,可以附加一个salt)如果我们假设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]