一个好的单次伪随机洗牌算法是什么？

Question

费雪-耶茨洗牌算法提供了一种很好的算法来在单次遍历中对长度为n的数组A进行洗牌：

For k = 1 to n
    Pick a random integer j from k to n
    Swap A[k] and A[j]

在这个算法中只需单次遍历，A 的条目将会均匀随机出现。

一个常见的搞砸此算法的方法是执行以下操作：

For k = 1 to n
    Pick a random integer j from 1 to n
    Swap A[k] and A[j]

这个算法单次通过后得到的分布不是均匀随机的，关于它的分布有一个很好的讨论在这篇文章中：这个破解乱序算法会得到什么样的分布？

我最近读了一篇名为分析赌场洗牌机的文章，作者描述了一个物理机器执行以下批量洗牌：

For k = 1 to n
    Pick a random integer j from 1 to 10
    Randomly choose to place card k on the top or bottom of stack j

作者要解决的问题是，是否在一次洗牌后可以得到相当随机的顺序。答案明显是否定的。看到这种洗牌方法的漏洞的一种方式是，从一副牌开始，其中有n/2张红色牌放在n/2张黑色牌之上。经过一次洗牌后的牌堆中最多只会有10个红色牌堆！对于n = 52*6，这不是非常随机。作者还表明，对于一次洗牌后的优化“猜下一张牌”的策略，平均而言，将正确猜测9.5张牌，而对于随机牌堆的最佳策略，平均而言只能正确猜测4.5张牌。

是否有其他有趣的单次洗牌方法可以实现接近随机的顺序和/或有趣的分布？我特别感兴趣的是类似于后者的批量条目洗牌。

- PengOne

---

非常有趣的问题，但我认为它不适合在SO上发布。 - Mitch Wheat

@Mitch，来吧...让我们保留一些有趣的问题！ - Dr. belisarius

@PengOne：一些洗牌理论也出现在“证明来自书本”的书中。 - Mitch Wheat

Fisher-Yates算法很简单，可能是正确的，并且一旦你理解了它，就是进行洗牌最直观的方法了。我们真的需要更多吗？ :) 在现实世界中（因此OT适用于SO），我想知道可以实现哪种最快的洗牌方式，可以获得好的分布。 - Nick Johnson

@TimPost：我认为这不需要将其标记为 CW，因为它不是一个购物清单问题。很不幸，由于标题中的“好”，它看起来很主观，但“什么是好的算法”与“什么是好的显示器”相差甚远。在这种情况下，可以用大O或Theta来量化。 - user616736

Answer 1

如果你有一副洗过的牌，想要将一批新牌洗入其中（并且你知道这些新牌中没有重复的牌），那么我认为以下方法是有效的。

ForEach card in batch:
    gap = random(deck.size() + 1)  # choose a gap between cards, before first, or after last.
    deck.insertAt(gap,card)

分布

随机分布是均匀的，牌堆的顺序不变，因此仍然是均匀的。我认为结果应该是均匀的。（我的统计知识太生疏了，不能确定）。

时间

假设insertAt是O(1)而不是O(N)——这取决于牌堆的实现——整个程序是O(批量大小)，这是你所能希望的最好情况，因为你必须处理每张牌。

- Ian