# Random shuffle

## The problem

Shuffling a list, i.e. creating a random permutation, is not easy to do correctly. Each permutation should have the same probability.

## Imperative algorithm

The standard imperative algorithm can be implemented as follows:

```import System.Random
import Data.Array.IO

-- | Randomly shuffle a list
--   /O(N)/
shuffle :: [a] -> IO [a]
shuffle xs = do
ar <- newArray n xs
forM [1..n] \$ \i -> do
j <- randomRIO (i,n)
writeArray ar j vi
return vj
where
n = length xs
newArray :: Int -> [a] -> IO (IOArray Int a)
newArray n xs =  newListArray (1,n) xs
```

Or one can use ST to avoid needing IO:

```import System.Random
import Data.Array.ST
import Data.STRef

-- | 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)
writeArray ar j vi
return vj
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.

## Other implemenations

### Drawing without replacement

• allows you to not shuffle the entire list but only part of it (drawing elements without replacement)
• allows you to take multiple drawings/shufflings at once, which can save some array building
```{- | @grabble xs m n@ is /O(m*n')/, where @n' = min n (length xs)@
Chooses @n@ elements from @xs@, without putting back,
and that @m@ times. -}
grabble :: MonadRandom m => [a] -> Int -> Int -> m [[a]]
grabble xs m n = do
swapss <- replicateM m \$ forM [0 .. min (maxIx - 1) n] \$ \i -> do
j <- getRandomR (i, maxIx)
return (i, j)
return \$ map (take n . swapElems xs) swapss
where
maxIx   = length xs - 1

grabbleOnce :: MonadRandom m => [a] -> Int -> m [a]
grabbleOnce xs n = head `liftM` grabble xs 1 n

swapElems  :: [a] -> [(Int, Int)] -> [a]
swapElems xs swaps = elems \$ runSTArray (do
arr <- newListArray (0, maxIx) xs
mapM_ (swap arr) swaps
return arr)
where
maxIx   = length xs - 1
swap arr (i,j) = do
```*Main MonadRandom Random> evalRand (grabble "abcdef" 6 3) (mkStdGen 0)