我一直在使用Random (java.util.Random)来洗牌一副52张牌。有52个!(8.0658175 e + 67)的可能性。然而,我发现java.util.Random的种子很长,它要小得多,为2^64 (1.8446744e+19)。

从这里开始,我怀疑java.util.Random是否真的那么随机;它真的能产生全部52个吗?可能性?

如果不是,我如何可靠地生成一个更好的随机序列,可以产生所有52!可能性?


当前回答

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

其他回答

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

random实现了一个算法,其模量为248,最大周期长度不超过248,因此远小于2226(对应于我提到的226位)。您将需要使用另一个周期长度更大的PRNG,特别是最大周期长度为52 !或更大的PRNG。

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

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


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

您的分析是正确的:在伪随机数生成器中植入任何特定的种子都必须在洗牌后产生相同的序列,从而将您可以获得的排列数量限制为264。这个断言很容易通过调用Collection进行实验验证。shuffle两次,传递一个用相同种子初始化的随机对象,并观察两次随机shuffle是相同的。

因此,解决这个问题的方法是使用允许更大种子的随机数生成器。Java提供了securerrandom类,可以使用大小几乎无限制的byte[]数组进行初始化。然后,您可以将securerrandom的一个实例传递给集合。洗牌完成任务:

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

我的实证研究成果是Java。随机并不完全是随机的。如果你尝试使用随机类" next高斯()方法,并生成足够大的样本总体的数字在-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欧元,从长远来看,对于经常赌博的人来说,这太贵了,不玩就会破产。即使你把优惠券分享给其他可以购买的客户,如果你想盈利,你也必须非常幸运。

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

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

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

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

If you're making a multiplayer card game, particularly if there's money on the line? Then you're going to need to do some googling on how the online poker sites handled the same problem you're asking about. Because while the low seed space issue isn't noticeable to the average player, it is exploitable if it's worth the time investment. (The poker sites all went through a phase where their PRNGs were 'hacked', letting someone see the hole cards of all the other players, simply by deducing the seed from exposed cards.) If this is the situation you're in, don't simply find a better PRNG - you'll need to treat it as seriously as a Crypto problem.

一个非常简单的算法是将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]