[Haskell-cafe] Linear Shuffle

[Okasaki, C. DR EECS]

Clearly, you can do a perfect shuffle in O(N) time using mutable arrays,
using the standard imperative algorithm.  You can also do it in O(N)
expected time using *immutable* arrays, using Haskell's bulk array
operations.

1. Start with a list of length N.  If N < 2, stop.
2. Pair each element with a random index in the range [1,2N] (or
[0,2N-1]).
3. Use "accum" to create an array of size 2N, where slot I contains a
list of all the elements paired with I.
4. Map the shuffle function recursively across the array to re-shuffle
any slots that got more than one element.
5. Append all the slots together into the result list.

If you leave out step 4, you get an algorithm that runs in O(N)
worst-case time, rather than expected time, but you no longer have a
perfect shuffle (although it might be good enough).  Upping the size of
the array from 2N to 3N or 4N will help reduce collisions, but will not
entirely eliminate them.

With step 4, you can imagine pathological cases where everything gets
put in the same slot, but with a reasonable random number generator, it
is vanishingly unlikely that you will have enough collisions to drive
the cost higher than linear.  Again, upping the size of the array from
2N to 3N or 4N makes this even more unlikely.

-- Chris