On Fri, 14 Jan 2005, Scott Turner wrote:
The shuffling algorithms mentioned so far are comparable to insertion/selection sort. I had come up with a shuffler that relates to quicksort, in that it partitions the input randomly into lists and works recursively from there. It looks efficient and works out well in Haskell.
I did some shuffling based on mergesort, that is a list is randomly split (unzipped) into two lists and the parts are concatenated afterwards. You must repeat this some times. It even works for infinite lists. It doesn't need IO.
randomPermute :: RandomGen g => [a] -> g -> ([a],g) randomPermute x g0 = let (choices,g1) = runState (mapM (const (State (randomR (False,True)))) x) g0 xc = zip x choices in (map fst (filter snd xc ++ filter (not . snd) xc), g1)