为什么这个改组算法错了？

Question

在我阅读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))

有人可以解释第一种算法是如何不正确的吗？(即不产生随机混乱).

Answer 1

来自维基百科:

类似地,在每次迭代中始终从整个有效数组索引范围中选择j也会产生偏差的结果,尽管不那么明显.这可以从这样的事实看出,即这样做产生了n ^个不同的可能的交换序列,而只有n!n元素阵列的可能排列.因为n ⁿ永远不能被n整除!当n> 2时(因为后者可以被n-1整除,它与n没有主要因子),所以一些排列必须由交换的n ^n个序列产生.作为这种偏见的一个具体例子,观察改组三元素阵列的可能结果的分布[1,2,3].这个数组有6种可能的排列(3!= 6),但算法产生27次可能的混洗(3 ³ = 27).在这种情况下,[1,2,3],[3,1,2]和[3,2,1]各自由27次洗牌中的4次产生,而剩余的3次排列中的每一次都发生在27次中的5次中.洗牌.

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