daily pastebin goal
22%
SHARE
TWEET

randomwalker

a guest Sep 16th, 2009 413 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import System.Random
  2. import Ix
  3.  
  4. -- general notes:
  5. --    1. is it really this painful to do anything with random numbers?
  6. --    2. the RNG doesn't even work very well, seems to be linear-congruential
  7. --       how do i get Mersenne Twister?
  8.  
  9. -- attempt 1: straightforward translation of standard idiom; quadratic time
  10. permute1 xs = permute_ xs (mkStdGen 0) where
  11.     permute_ [] rgen = []
  12.     permute_ xs rgen = let (idx, newrgen) = randomR (1, length xs) rgen in
  13.                        xs!!(idx-1) : permute_ (take (idx-1) xs ++ drop idx xs) newrgen
  14.  
  15. -- attempt 2: decorate-sort-undecorate
  16. permute2 xs = permute_ xs (iteraternd (mkStdGen 0) random) where
  17.     -- had to force input type to Int because
  18.     -- i can't figure out what's the base class for sortable types
  19.     permute_ :: [Int] -> [Int] -> [Int]
  20.     permute_ xs rnds = map snd (qsort (zip rnds xs)) where
  21.         -- why does 'sort' work in the prelude but not here?
  22.         qsort [] = []
  23.         qsort (x:xs) = qsort (filter (<=x) xs) ++ [x] ++ qsort (filter (>x) xs)
  24.     -- i'm hoping this is somewhere in the library and i've missed it
  25.     iteraternd g rnd = let (val, newg) = rnd g in val : iteraternd newg rnd
  26.  
  27. -- attempt 3: not really sure where i was going with this..
  28. -- neither linear-time nor a perfect shuffle
  29. -- strategy is to split in half, permute each, and merge 'randomly'
  30. permute3 xs = permute_ xs (mkStdGen 0) where
  31.     permute_ []  rgen = []
  32.     permute_ [x] rgen = [x]
  33.     permute_ xs  rgen =
  34.         let mid = (length xs) `div` 2; (rgen1, rgen2) = split rgen in
  35.         merge (permute_ (take mid xs) rgen1)
  36.               (permute_ (drop mid xs) rgen2)
  37.               []
  38.               rgen
  39.     -- acc is needed to make merge tail-recursive
  40.     merge xs [] acc rgen = xs ++ acc
  41.     merge [] ys acc rgen = ys ++ acc
  42.     merge (x:xs) (y:ys) acc rgen =
  43.         let (rnd, newrgen) = randomR (0,1) rgen :: (Int, StdGen) in
  44.         if rnd == 0
  45.             then merge xs ys (x:y:acc) newrgen
  46.             else merge xs ys (y:x:acc) newrgen
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top