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