5

你会说现代版的 Fisher yates 是最公正的洗牌算法吗？你如何解释数组中的每个元素都有 1/n 的概率位于其原始位置？

4

2 回答 2

8

给定一个完美的伪随机数生成器（Mersenne Twister非常接近），Fisher-Yates 算法是完全无偏的，因为每个排列都有相同的发生概率。使用归纳法很容易证明这一点。Fisher-Yates 算法可以递归编写如下（在 Python 语法伪代码中）：

def fisherYatesShuffle(array):
    if len(array) < 2:
        return

    firstElementIndex = uniform(0, len(array))
    swap(array[0], array[firstElementIndex])
    fisherYatesShuffle(array[1:])

每个索引都有相同的概率被选为firstElementIndex。当你递归时，你现在有相同的概率选择任何剩余的元素。

编辑：该算法已在数学上被证明是无偏的。由于该算法是不确定的，因此测试实现是否正常工作的最佳方法是统计。我会取一个任意但很小的数组，将它洗牌很多次（每次从与输入相同的排列开始）并计算每个输出排列发生的次数。然后，我会使用Pearson 的卡方检验来测试这个分布的均匀性。

于 2010-03-17T01:14:37.880 回答
4

（现代，又名“Knuth”）Fisher-Yates shuffle 是

  • 实现起来相对简单
  • 相当有效的时间 O(n) 和 O(1) 或实际上 O(0) 的空间
  • 无偏的（每个排列都是等概率的）
  • 众所周知/很好理解，经过验证，经过测试。

我们还想从算法中得到什么（嗯，是的，当排列的数量变得巨大时，人们可能会尝试其他方法，但大多数情况并不涉及如此巨大的计数）？

编辑：'刚刚注意到这个答案回应了问题的标题，而不是它的内容。（这就是为什么最好让问题的这两个部分更好地匹配......）
简而言之，随机播放将与用于实现算法的特定 RNG 一样随机。
一个直观的解释是，对于具有 m 个元素的数组，即使作为 n，循环的递减控制变量下降到 1，位置 n 的单元格可能被交换的可能单元格减少，这个单元格的概率很容易被移动以完全相同的比例增加。换句话说，数组的最后一个元素可以在数组中的任何位置结束，但它只有一次移动的机会（在第一次迭代时）。要移动的倒数第二个元素少了一个位置，但有 1/m 的概率它可能在第一次迭代期间很容易被移动。等等

于 2010-03-17T01:13:57.727 回答