Re: How to make a random permutation

[ebrandt@muddcs.cs.hmc.edu (Eli Brandt)]

Eric Hughes said:
> I continue to be amazed at how few people know an algorithm to
> generate a truly random permutation efficiently.

The slowest one I've seen in code is "pick at random until you
get an unchecked element; select it and check it off."  What's
worse is how many people know algorithms that they *think*
generate true-random permutations, but which don't.  They are
sometimes good approximations in practice, but it irks me.

1. Assign a random tag to each element.  Sort on these.
2. The one you responded to: do a large number of swaps.
3. Sort, using a random bit generator as a comparator function.
   (This one is actually in Schneier.)

Why?
1. Tag collisions.
2. Asymptotic at best.
3. Counting argument.

Elaboration is left as an exercise, etc. etc.

   Eli   ebrandt@hmc.edu