生成一个统一的随机置换 [英] Generate an uniform random permutation

问题描述

我不知道下面的伪code是否可以生成一个均匀随机置换：

I am not sure whether the following pseudo-code can generate an uniformly random permutation:

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

这似乎是对的，但任何人都可以给我一个严格的证明来验证其正确性或不正当性？

It seems to be right, but can anyone give me a rigorous proof to verify its correctness or wrongness ?

推荐答案

这个解决方案是有偏差的，你想的费雪耶茨算法 [类似于]非偏置换。 [基本上，你需要换用随机的（I，N），而不是用随机（1，N）]

This solution is biased, you want the Fisher Yates algorithm [which is similar] for non biased permutation. [basically, you need to swap with random(i,n) instead of with random(1,n)]

这个线程讨论如何以及为什么你的解决方案是有偏差的。

This thread discusses how and why your solution is biased.

这篇关于生成一个统一的随机置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！