[Haskell-cafe] Linear shuffle
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:
More information about the Haskell-Cafe