Efficient Random Permutations
-----------------------------

Given an array (x1, x2, x3, ..., xN), it is possible to create a random permutation
by (1) writing out a list of n random numbers, (r1, r2, r3, ..., rN), (2) sorting
the list in ascending order, and carrying along the x's in parallel.

This is not an efficient way to create random permutations, because the process
of sorting a list of numbers uses a lot of computer time.  Some sorting algorithms
are more efficient than others; the bubble sort is rather inefficient, requiring
N * (N - 1) comparisons and moves.

It is possible to create a random permutation with almost no comparisons, and
with the number of moves being of order N.

Here is how this is done.

Assume you have two rows of boxes.  In the first row of boxes there are the
N numbers 1, 2, 3, ... N in order.

The second row of boxes is empty.

Begin by randomly choosing one number from the Row 1 and putting it in
the first box in Row 2.  Say that number came from the i-th box in Row 1.

Then take the number which is in the last position in Row 1.  Put
it into the i-th (now empty) box in Row 1.  Row 1 now has the first
N - 1 boxes nonempty and the remaining box is empty.

For the next step, choose a box randomly from the first N - 1 nonempty
boxes in Row 1.  Put the contents into the SECOND position in Row 2.
Again move the contents of the (N - 1)th box in Row 1 into the box
that was just vacated.

Keep doing this.  When you have finished, Row 2 is a random permutation
of Row 1.

This illustrates a general principle: usually it is easier to scramble 
something than it is to unscramble it.