Advanced Puzzlers - Java Puzzlers: Traps, Pitfalls, and Corner Cases - page 293

< Day Day Up >
Puzzle 94: Lost in the Shuffle
The following shuffle method purports to shuffle its input array fairly. In other words, it purports
to generate all permutations with equal likelihood, assuming that the underlying pseudorandom
number generator is fair. Does it make good on its promise? If not, how do you fix it?
import java.util.Random;
public class Shuffle {
private static Random rnd = new Random();
public static void shuffle(Object[] a) {
for (int i = 0; i < a.length; i++)
swap(a, i, rnd.nextInt(a.length));
}
private static void swap(Object[] a, int i, int j) {
Object tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
Solution 94: Lost in the Shuffle
Looking at the shuffle method, there's nothing obviously wrong with it. It iterates through the
array, swapping a randomly chosen element from the array into each location. That ought to shuffle
the array fairly, right? Wrong. There's a big difference between saying "There's nothing obviously