algorithm - 为什么 fisher yates 是最有用的洗牌算法？

Question

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

Answer 1

给定一个完美的伪随机数生成器(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's Chi-square Test测试此分布的均匀性。