Random shuffle
From HaskellWiki
(Difference between revisions)
(Random shuffle algorithm) |
(Add pure version using ST) |
||
| Line 26: | Line 26: | ||
writeArray ar j vi | writeArray ar j vi | ||
return vj | return vj | ||
| + | </haskell> | ||
| + | |||
| + | Or one can use ST to avoid needing IO: | ||
| + | |||
| + | <haskell> | ||
| + | -- | Randomly shuffle a list without the IO Monad | ||
| + | -- /O(N)/ | ||
| + | shuffle' :: [a] -> StdGen -> ([a],StdGen) | ||
| + | shuffle' xs gen = runST (do | ||
| + | g <- newSTRef gen | ||
| + | let randomRST lohi = do | ||
| + | (a,s') <- liftM (randomR lohi) (readSTRef g) | ||
| + | writeSTRef g s' | ||
| + | return a | ||
| + | ar <- newArray n xs | ||
| + | xs' <- forM [1..n] $ \i -> do | ||
| + | j <- randomRST (i,n) | ||
| + | vi <- readArray ar i | ||
| + | vj <- readArray ar j | ||
| + | writeArray ar j vi | ||
| + | return vj | ||
| + | gen' <- readSTRef g | ||
| + | return (xs',gen')) | ||
| + | where | ||
| + | n = length xs | ||
| + | newArray :: Int -> [a] -> ST s (STArray s Int a) | ||
| + | newArray n xs = newListArray (1,n) xs | ||
| + | </haskell> | ||
| + | |||
| + | And if you are using IO's hidden StdGen you can wrap this as usual: | ||
| + | |||
| + | <haskell> | ||
| + | shuffleIO :: [a] -> IO [a] | ||
| + | shuffleIO xs = getStdRandom (shuffle' xs) | ||
</haskell> | </haskell> | ||
Revision as of 20:49, 18 October 2007
1 The problem
Shuffling a list, i.e. creating a random permutation, is not easy to do correctly. Each permutation should have the same probability.
2 Imperative algorithm
The standard imperative algorithm can be implemented as follows:
{-# LANGUAGE ScopedTypeVariables #-} import System.Random import Data.Array.IO import Control.Monad -- | Randomly shuffle a list -- /O(N)/ shuffle :: forall a. [a] -> IO [a] shuffle xs = do let n = length xs ar <- newListArray (1,n) xs :: IO (IOArray Int a) forM [1..n] $ \i -> do j <- randomRIO (i,n) vi <- readArray ar i vj <- readArray ar j writeArray ar j vi return vj
Or one can use ST to avoid needing IO:
-- | Randomly shuffle a list without the IO Monad -- /O(N)/ shuffle' :: [a] -> StdGen -> ([a],StdGen) shuffle' xs gen = runST (do g <- newSTRef gen let randomRST lohi = do (a,s') <- liftM (randomR lohi) (readSTRef g) writeSTRef g s' return a ar <- newArray n xs xs' <- forM [1..n] $ \i -> do j <- randomRST (i,n) vi <- readArray ar i vj <- readArray ar j writeArray ar j vi return vj gen' <- readSTRef g return (xs',gen')) where n = length xs newArray :: Int -> [a] -> ST s (STArray s Int a) newArray n xs = newListArray (1,n) xs
And if you are using IO's hidden StdGen you can wrap this as usual:
shuffleIO :: [a] -> IO [a] shuffleIO xs = getStdRandom (shuffle' xs)
This is a lot simpler than the purely functional algorithm linked below.
