Randomization - Data Structures and Problem Solving Using Java - page 405

through the deck. We want the shuffle to be fair. That is, each of the 52! possible
orderings of the deck should be equally likely as a result of the shuffle.

This type of problem involves the use of a random permutation. In general,
the problem is to generate a random permutation of 1, 2, ..., N , with all permuta-
tions being equally likely. The randomness of the random permutation is, of
course, limited by the randomness of the pseudorandom number generator. Thus
all permutations being equally likely is contingent on all the random numbers
being uniformly distributed and independent. We demonstrate that random per-
mutations can be generated in linear time, using one random number per item.
A routine, permute , to generate a random permutation is shown in
Figure 9.7. The loop performs a random shuffling. In each iteration of the loop,
we swap a[j] with some array element in positions 0 to j (it is possible to per-
form no swap).

A random permuta-
tion can be gener-
ated in linear time,
using one random
number per item.

Clearly, permute generates shuffled permutations. But are all permutations
equally likely? The answer is both yes and no. The answer, based on the algo-
rithm, is yes. There are N ! possible permutations, and the number of different
possible outcomes of the N - 1 calls to nextInt at line 11 is also N ! The reason is
that the first call produces 0 or 1, so it has two outcomes. The second call pro-
duces 0, 1, or 2, so it has three outcomes. The last call has N outcomes. The total
number of outcomes is the product of all these possibilities because each ran-
dom number is independent of the previous random numbers. All we have to
show is that each sequence of random numbers corresponds to only one permu-
tation. We can do so by working backward (see Exercise 9.6).
However, the answer is actually no—all permutations are not equally
likely. There are only 2 31 - 2 initial states for the random number generator,
so there can be only 2 31 - 2 different permutations. This condition could be a
problem in some situations. For instance, a program that generates 1,000,000
permutations (perhaps by splitting the work among many computers) to mea-
sure the performance of a sorting algorithm almost certainly generates some
permutations twice—unfortunately. Better random number generators are
needed to help the practice meet the theory.

The correctness of
permute is subtle.

figure 9.7
A permutation routine

1 /**
2 * Randomly rearrange an array.
3 * The random numbers used depend on the time and day.
4 * @param a the array.
5 */
6 public static final void permute( Object [ ] a )
7 {
8 Random r = new Random( );
9
10 for( int j = 1; j < a.length; j++ )
11 swapReferences( a, j, r.nextInt( 0, j ) );
12 }