SHARE

TWEET

# randomwalker

a guest
Sep 16th, 2009
413
Never

**Not a member of Pastebin yet?**

**, it unlocks many cool features!**

__Sign Up__- 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 = []
- -- 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
- -- why does 'sort' work in the prelude but not here?
- qsort [] = []
- -- 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 =
- []
- 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 =
- if rnd == 0
- then merge xs ys (x:y:acc) newrgen
- 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.