Here is the procedure discussed in class for generating a random permutation of an array of elements a[1], a[2],...a[n]:

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.

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