1. for i = 2 to n
2.     generate a random integer, j, in the range 1..i
3.     swap a[i] and a[j]

The other procedure proposed in class, where j would always be in the range 1..n in fact doesn't produce uniformly random permutations:

Suppose n = 3 and a[i] = i. After the first swap, the following are equally likely: 123, 213, 321. After the second swap, these lead to {213, 123, 132}, {123, 213, 231}, and {231, 321, 312}, respectively, so 132, 321, and 312 are less likely than the other permutations. After the third swap, these lead to 312, 231, 213, 321, 132, 123, 231, 123, 132, 321, 132, 123, 312, 231, 213, 132, 213, 231, 132, 213, 231, 123, 312, 321, 213, 321, 312, respectively. The probabilities are:

• P(123) = 4/27
• P(132) = 5/27
• P(213) = 5/27
• P(231) = 5/27
• P(312) = 4/27
• P(321) = 4/27

Another point discussed in class was that one cannot just take the RC4 value mod 6 to get a uniform random integer between 0 and 5, since the values 0 through 3 will be slightly more frequent. One way to get the correct distribution is to throw out all RC4 values that are 252 or larger. The following table gives the results of programming both approaches and generating three million random values. The numbers in the table are deviations from the expected value of 500,000.

Correct	RC4 mod 6
686	3567
693	4414
-1283	4491
-510	3378
320	-7527
94	-8323