Tạo một hoán vị ngẫu nhiên thống nhất

Question

Tôi không chắc chắn liệu pseudo-code sau đây có thể tạo ra một uniformly random permutation:

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

Nó có vẻ là đúng, nhưng bất cứ ai có thể cho tôi một bằng chứng khắt khe để xác minh tính đúng đắn hay sai của nó ?

Answer 1

Giải pháp này là thiên vị, bạn muốn Fisher Yates algorithm [tương tự] cho hoán vị không thiên vị. [về cơ bản, bạn cần trao đổi với random(i,n) thay vì với random(1,n)]

This thread thảo luận cách thức và lý do giải pháp của bạn bị thiên vị.