为什么渔民是最有用的改组算法？

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的卡方检验来测试这种分布的均匀性.

Answer 2

（现代，又名“Knuth”）Fisher\xe2\x80\x93Yates洗牌是

\n\n

\n
• 实施起来相对简单
\n
• 时间上相当高效的 O(n)，空间上的 O(1) 甚至 O(0)
\n
• 无偏（每个排列都是等概率的）
\n
• 众所周知/充分理解、经过验证、经过测试。
\n

\n\n

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

\n\n

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

\n