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:
http://groups-beta.google.com/group/comp.lang.functional/browse_frm/thread/570615e64e3e4fc0
-- Ben
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
