[Haskell-cafe] Linear shuffle

Ben Rudiak-Gould Benjamin.Rudiak-Gould at cl.cam.ac.uk
Sat Jan 15 12:25:21 EST 2005

Scott Turner wrote:

 >Analogous to quicksort's bad behavior in the worst case, an invocation of
 >'partition' is not guaranteed to make any progress with the shuffling,
 >because one of the output lists might receive all of the input items.

It's worse than quicksort, because there's no guarantee that the 
algorithm will ever terminate. But this is actually optimal--there's no 
way to perfectly shuffle a list using a bounded number of coin flips, 
because n! doesn't divide any power of 2 for n>=3.

I posted this algorithm on comp.lang.functional a while ago:


-- Ben

More information about the Haskell-Cafe mailing list