algorithm - 生成均匀随机排列

Question

我不确定以下伪代码是否可以生成均匀随机排列:

PERMUTATE(A): 
    n = A.length
    for i = 1 to n
        swap A[i] and A[random(1,n)]

好像是对的，但是谁能给我一个严格的证明来验证它的正确性或错误性？

Answer 1

这个解决方案是有偏见的，你想要 Fisher Yates algorithm [这是相似的] 无偏排列。 [基本上，您需要使用 random(i,n) 而不是 random(1,n)]

This thread讨论您的解决方案如何以及为何存在偏见。