生成均匀的随机排列

Question

我不确定以下伪代码是否可以生成uniformly random permutation:

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

这似乎是对的,但任何人都可以给我一个严格的证据来验证其正确性或错误吗？

Answer 1

这个解决方案存在偏差,你希望Fisher Yates算法 [类似]用于非偏置置换.[基本上,你需要交换random(i,n)而不是与random(1,n)]

该主题讨论了解决方案偏向的方式和原因.