生成一個統一的隨機排列

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 algorithm [這是類似的]非偏置排列。 [基本上，您需要與random(i,n)對換，而不是與random(1,n)]

This thread討論了您的解決方案如何以及爲何存在偏見。