[Haskell-cafe] Linear shuffle

[Ben Rudiak-Gould]

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