13

当我需要在 Java/Android 中洗牌时，我Collections.shuffle(List<?> list)当然会使用 . 我曾经这样做过，结果似乎可以接受。但他们不是。

如本文所述，共有 52 个！52张扑克牌的可能独特的洗牌。这相当于大约 2^226。

但默认使用Collections.shuffle(List<?> list)48位种子，因此只能创建 2^48 个唯一的随机播放 - 这只是所有可能随机播放的百分比！new Random()3.49*10^(-52)

那么如何正确洗牌呢？

我已经开始使用SecureRandom了，但最后就够了吗？

List<Card> cards = new ArrayList<Card>();
...
SecureRandom secureRandom;
try {
    secureRandom = SecureRandom.getInstance("SHA1PRNG");
}
catch (NoSuchAlgorithmException e) {
    secureRandom = new SecureRandom();
}
secureRandom.nextBytes(new byte[20]); // force SecureRandom to seed itself
Collections.shuffle(cards, secureRandom);
4

5 回答 5

4

您可能只能从特定的起始安排中获得 2 48手不同的牌，但并不要求您每次都以相同的安排开始。

大概，在牌组完成后（扑克牌、二十一点等），它的顺序是不确定的，任何一种重新排列都是合适的。

而且，如果您担心每次启动程序时都从固定排列开始，只需在退出时保持顺序并下次重新加载即可。

无论如何，2 48仍然是大量的可能性（大约 280,000,000,000,000），对于纸牌游戏来说绰绰有余，当您意识到它限制了洗牌而不是安排时更是如此。除非您是认真的统计学家或密码学家，否则您所拥有的应该没问题。

于 2013-05-03T14:52:58.603 回答
2

尽管您使用的是SecureRandom, 仍然有一个有限的状态。只要输入种子的范围小于 52！它不可能是完全随机的。

事实上，SHA1PRNG是 160 位种子，这意味着它仍然不够随机。按照这个链接，它在几年前就有一个解决方案，方法是使用名为UnCommons Math.

于 2013-05-03T14:47:05.067 回答
1

如果你想要真正的随机性，你可以跳过伪随机生成器并选择更好的东西，比如从大气噪声生成的随机数。

random.org提供了一个API，可以将这种方式生成的随机数集成到您自己的软件中。

于 2013-05-03T15:23:51.570 回答
0

如何真正洗牌？

有几种洗牌技术。

任一（剥离/上手）：

Cut the deck in two
    Add a small (pseudorandom) amount of one half to the front of the front of the other
    Add a small (pseudorandom) amount of one half to the front of the back of the other
Do this until one hand is empty
Repeat

或（步枪）：

Cut the deck in two
    Set down a small (pseudorandom) portion of one half
    Set down a small (pseudorandom) portion of the other
Do this until both hands are empty, and you have a new deck
Repeat

除此之外，还有更多，如我上面的链接中所述。

无论如何，有如此多的组合，即使是完美的洗牌算法也需要一台机器2*10^50每秒探索独特的排列，才能完成探索宇宙存在时间内的每一个排列。到 2019 年，现代计算机预计只能达到 1 ExaFLOP（1*10^18每秒浮点运算）。

也没有人类洗牌器会探索这种可能性，而且我相信（在最基本的层面上）你是在模拟人类洗牌，对吗？您是否会发现荷官可能会在一次洗牌中将递增顺序的牌组洗牌为降序？在一次洗牌中以偶数排位在奇数排位之前拆分牌组？

我不认为2^48在每次洗牌中将自己限制在该相空间的一个（尽管非常）小部分（可能的随机数）中是不可接受的，只要您不以相同的方式连续播种等。

在 52 张卡片组中，恰好有 52 个阶乘（简写为 52！）可能的卡片排序。这大约是 8×10 67 个可能的排序，或者具体来说： 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000.
这个数字的大小意味着，即使在宇宙历史上，两个随机选择的、真正随机的牌组也不太可能是相同的。然而，虽然随机牌组中所有牌的确切顺序是不可预测的，但有可能对未充分随机化的牌组做出一些概率预测。
〜维基百科

此外，值得注意的是，Bayer & Diaconis 在 1992 年证明只需 7 次良好的洗牌即可正确随机化一副​​牌，这是维基百科中关于它的部分，其中有很多讨论此问题的论文的链接。

于 2013-06-29T00:30:48.913 回答
0

从您链接的文章中窃取答案：

START WITH FRESH DECK
GET RANDOM SEED
FOR CT = 1, WHILE CT <= 52, DO
X = RANDOM NUMBER BETWEEN CT AND 52 INCLUSIVE
SWAP DECK[CT] WITH DECK[X]

随机数生成器应该是好的，并且使用一个 64 位的种子，你无法预测地选择，最好使用硬件。

于 2013-05-03T14:53:30.623 回答