生成一个均匀随机排列

Question

9

我不确定以下伪代码是否能生成一个 均匀随机排列：

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

看起来是对的，但有没有人能给我一个严谨的证明来验证它的正确性或错误性？

- Flybywind

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

这个方案存在偏差，你需要使用Fisher Yates算法[相似但无偏差的置换]。[基本上，你需要用random(i,n)而不是random(1,n)来进行交换]

这个帖子讨论了为什么你的解决方案存在偏差。