- import System.Random
- import Ix
- -- general notes:
- -- 1. is it really this painful to do anything with random numbers?
- -- 2. the RNG doesn't even work very well, seems to be linear-congruential
- -- how do i get Mersenne Twister?
- -- attempt 1: straightforward translation of standard idiom; quadratic time
- permute1 xs = permute_ xs (mkStdGen 0) where
- permute_ [] rgen = []
- permute_ xs rgen = let (idx, newrgen) = randomR (1, length xs) rgen in
- xs!!(idx-1) : permute_ (take (idx-1) xs ++ drop idx xs) newrgen
- -- attempt 2: decorate-sort-undecorate
- permute2 xs = permute_ xs (iteraternd (mkStdGen 0) random) where
- -- had to force input type to Int because
- -- i can't figure out what's the base class for sortable types
- permute_ :: [Int] -> [Int] -> [Int]
- permute_ xs rnds = map snd (qsort (zip rnds xs)) where
- -- why does 'sort' work in the prelude but not here?
- qsort [] = []
- qsort (x:xs) = qsort (filter (<=x) xs) ++ [x] ++ qsort (filter (>x) xs)
- -- i'm hoping this is somewhere in the library and i've missed it
- iteraternd g rnd = let (val, newg) = rnd g in val : iteraternd newg rnd
- -- attempt 3: not really sure where i was going with this..
- -- neither linear-time nor a perfect shuffle
- -- strategy is to split in half, permute each, and merge 'randomly'
- permute3 xs = permute_ xs (mkStdGen 0) where
- permute_ [] rgen = []
- permute_ [x] rgen = [x]
- permute_ xs rgen =
- let mid = (length xs) `div` 2; (rgen1, rgen2) = split rgen in
- merge (permute_ (take mid xs) rgen1)
- (permute_ (drop mid xs) rgen2)
- []
- rgen
- -- acc is needed to make merge tail-recursive
- merge xs [] acc rgen = xs ++ acc
- merge [] ys acc rgen = ys ++ acc
- merge (x:xs) (y:ys) acc rgen =
- let (rnd, newrgen) = randomR (0,1) rgen :: (Int, StdGen) in
- if rnd == 0
- then merge xs ys (x:y:acc) newrgen
- else merge xs ys (y:x:acc) newrgen