9

在我阅读 Fisher-Yates 之前，这是我想出的算法：

def sort(arr):
    for i in range(len(arr)):
        swap(arr, i, rand.randint(0, len(arr) - 1))

据我了解，这与 Fisher-Yates 之间的唯一区别在于：

swap(arr, i, rand.randint(0, len(arr) - 1))

我应该写：

swap(arr, i, rand.randint(i, len(arr) - 1))

有人可以解释第一个算法是如何不正确的吗？（即不产生随机洗牌）。

4

1 回答 1

12

来自维基百科：

类似地，每次迭代时总是从有效数组索引的整个范围中选择 j 也会产生有偏差的结果，尽管不太明显。这可以从这样一个事实中看出，这样做会产生 n n 个不同的可能交换序列，而只有 n！n 元素数组的可能排列。因为 n n永远不能被 n 整除！当 n > 2 时（因为后者可被 n−1 整除，它与 n 没有质因数），一些排列必须由更多的 n n交换序列比其他序列。作为这种偏差的一个具体例子，观察对三元素数组 [1, 2, 3] 进行洗牌的可能结果的分布。该数组有 6 种可能的排列 (3! = 6)，但该算法产生 27 种可能的 shuffle (3 3 = 27)。在这种情况下，[1, 2, 3], [3, 1, 2] 和 [3, 2, 1] 分别来自 27 次随机播放中的 4 次，而其余 3 次排列中的每一次出现在 27 次随机播放中的 5 次洗牌。

从本质上讲，您在 shuffle 中引入了一种微妙的偏差，这将导致一些排列比其他排列更频繁地出现。它通常不是很明显，但它可能使一些敏感的应用程序（例如排列的蒙特卡洛模拟）无法产生准确的答案。

于 2012-08-24T03:50:44.630 回答