我不确定以下伪代码是否可以生成均匀随机排列
:
PERMUTATE(A):
n = A.length
for i = 1 to n
swap A[i] and A[random(1,n)]
好像是对的,但是谁能给我一个严格的证明来验证它的正确性或错误性?
最佳答案
这个解决方案是有偏见的,你想要 Fisher Yates algorithm [这是相似的] 无偏排列。 [基本上,您需要使用 random(i,n)
而不是 random(1,n)
]
This thread讨论您的解决方案如何以及为何存在偏见。
关于algorithm - 生成均匀随机排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7902391/