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

It's easy to prove this method fair by induction. For the base case, observe that it is trivially fair for
an array of length 0. For the induction step, if you apply the method to an array of length n > 0, it
correctly selects a random element for the zeroth position of the result array. Then, it iterates over
the remainder of the array: At each position, it selects an element chosen at random from the
"subarray" beginning at that position and extending to the end of the original array. But that is
exactly what the method would do if it were applied directly to the subarray of length n - 1, starting
at position 1 in the original array. This completes the proof. It also suggests a recursive formulation
of the shuffle method, whose details are left as an exercise for the reader.
You might think that that's all there is to this story, but there's one final chapter. Do you suppose
that the fixed shuffle method generates all permutations of a 52-card deck, represented as a 52-
element array, with equal likelihood? After all, we just proved it fair. It probably won't surprise you
at this point that the answer is an emphatic no. The problem is that we assumed, way back at the
start of the puzzle, that "the underlying pseudorandom number generator is fair." It isn't.
The random number generator, java.util.Random , takes a 64-bit seed, and the sequence of
numbers it generates is fully determined by that seed. There are 52! permutations of a 52-card deck,
but only 2 64 seeds. What fraction of the permutations does that cover? Would you believe 2.3 x 10 -
47 percent? That is a polite way of saying "practically none." If you use
java.security.SecureRandom in place of java.util.Random , you get a 160-bit seed, but that buys
you surprisingly little: The shuffle method still fails to return some permutations for arrays with
more than 40 elements (because 40! > 2 160 ). For a 52-element array, you still get only 1.8 x 10 -18
percent of the possible permutations.
Does that mean that you shouldn't trust these pseudorandom number generators for shuffling cards?
It depends. They generate a negligible fraction of the possible permutations, but they have no
systematic bias that we're aware of. It seems fair to say that these generators are good enough for
casual use. If you need a state-of-the-art random number generator, you'll have to look elsewhere.
In summary, shuffling an array, like many algorithms, is tricky. It's easy to get it wrong and hard to
tell that you did. All other things being equal, you should use trusted libraries in preference to
handwritten code. If you want to learn more about the issues discussed in this puzzle, see [Knuth98
3.4.2].
< Day Day Up >