生成统一的随机排列


问题内容

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

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

这似乎是对的,但是谁能给我一个严格的证明,以验证其正确性或错误性?


问题答案:

这个解决方案是有偏见的,您想要非偏见排列的Fisher
Yates算法
(类似)。[基本上,您需要与交换random(i,n)而不是与random(1,n)]