[Haskell-cafe] Linear shuffle

[Henning Thielemann]

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)