为什么 Fisher Yates 是最有用的洗牌算法？

您认为现代版本的 Fisher Yates 是最公正的洗牌算法吗？ 您如何解释数组中每个元素位于其原始位置的概率为 1/n？

给定一个完美的伪随机数生成器（梅森扭转者 http://en.wikipedia.org/wiki/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。当您递归时，您现在有相同的概率选择仍然剩下的任何元素。

编辑：算法已被数学证明是无偏的。由于该算法是不确定的，因此测试是否存在的最佳方法执行统计上工作正常。我会采用一些任意但小尺寸的数组，将其洗牌多次（每次都以与输入相同的排列开始）并计算每个输出排列发生的次数。然后，我会用皮尔逊卡方检验 http://en.wikipedia.org/wiki/Pearson%27s_chi-square_test测试此分布的均匀性。