• API
• FAQ
• Tools
• Archive
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.

Top