**for***i*= 2**to***n*- generate a random integer,
*j*, in the range 1..*i* - 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 |