什么是好的一次性伪随机洗牌？

Question

Fisher-Yates shuffle 提供了一个很好的算法来对数组进行洗牌<单次传递长度为 n 的 code>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]

通过该算法单次传​​递的结果分布不是均匀随机，这篇文章对它是什么进行了很好的讨论：< a href="https://stackoverflow.com/questions/5131341/what-distribution-do-you-get-from-this-broken-random-shuffle">你从这个破碎的随机洗牌中得到什么分布？

我最近读过Diaconis、Fulman 和 Holmes 撰写的一篇令人愉快的文章，题为 赌场货架洗牌机分析，其中作者描述了一种物理执行以下批量洗牌的机器：

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 张牌。

是否有任何其他有趣的单遍洗牌可以实现近乎随机和/或有趣的分布？我对类似于后者的批量条目的洗牌特别感兴趣。

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(batch size) - 这是您可以希望的最好结果，因为您必须处理每张卡。