# How to randomly sort a sequence efficiently and simply?

Let me ask whether my instant simple algorithm has serious flaws ,for cryptography use, or not. Which is supposed to randomly change the order on a given sequence S[1..n] of the length n. Assume I have a good random number generator random() which returns a random integer in the range [1..n].

while true
for i in 1..n
r=random()
swap S[i] and S[r]


If it does not have serious flaws , when can I finish the while loop? Is there any well known algorithm which also easy to write a computer program?

Thank you in advance.

-
See Fisher-Yates shuffle and this previous question. Also, you probably shouldn't write cryptography routines unless you really know what you're doing. – Rahul Mar 4 '12 at 15:44
Note that with the Fisher-Yates shuffle, the outer "while" loop is unnecessary. Simply going through the "for" loop a single time will do a perfect job (assuming that your random number generator is cryptographically secure and you don't make any mistakes). – Tanner Swett Mar 4 '12 at 15:58
@TannerL.Swett: Your comment is not very clear. The "for" loop must be like in the Fisher-Yates shuffle (with random generating a number in a varying range, for instance from $1$ to $i$ if you want to use the swap of the example given here); using random with a fixed range as the question seems to imply just won't do. Also if $n$ is quite large and you want all permutations to be possible ("a prefect job"), then you are almost asking the impossible for the state space of a pseudo-random number generator (but that is independent of the shuffling algorithm). – Marc van Leeuwen Mar 4 '12 at 17:00
@Marc You're right; let me try to be more clear. @seven's algorithm tries to be more effective by shuffling multiple times; that's what the line "while true" is for. Sure enough, if a shuffling algorithm produces a non-uniform distribution, then repeating it is likely to produce a more uniform result. The Fisher-Yates shuffle, however, is uniform, so there's no reason to apply the FY shuffle multiple times, as long as your PRNG is itself secure. – Tanner Swett Mar 5 '12 at 1:40

The algorithm you suggest will not give you uniform distribution, so I guess it's not really what you want. A simple reason is that there are $n^n$ possible and equally probable runs of the algorithm (you choose a random number in $[1..n]$ and you do it $n$ times), while there are $n!$ different permutations. Since $n! \not | \ \ n^n$, it is certain that some permutations will get a larger chance of being chosen (though I don't have a clue which ones these are).