The discussion of randomly permuting a list comes up every few years.
Here's
what I wrote last time (2005):
"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."
Now, you can consider it cheating to say this is O(N) expected time
because it uses O(N log N) random bits. Fair enough. It is O(N) to the
same extent that the ordinary imperative algorithm is O(N), albeit
expected
rather than worst case.
-- Chris
_______________________________________________
Haskell-Cafe mailing list
Haskell-C...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
