什么是一个好的一次伪随机随机播放？

Question

所述费-耶茨洗牌给出了一个很好的算法洗牌的阵列A长度的n在单次通过:

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]

单次通过这个算法得到的分布并不是一成不变的,并且对这篇文章的内容进行了很好的讨论:你从这个破碎的随机混乱中获得了什么分布？

我最近阅读了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张牌.

有没有其他有趣的单通道随机播放实现近乎随机性和/或有趣的分布？我对类似于后者的shuffle特别感兴趣,它可以使用批量条目.

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