Bug in random shuffle algorithm

8 May 2017

      https://wiki.haskell.org/Random_shuffle says:

Here's a variation using the MonadRandom package:

import Control.Monad
import Control.Monad.ST
import Control.Monad.Random
import System.Random
import Data.Array.ST
import GHC.Arr

shuffle :: RandomGen g => [a] -> Rand g [a]
shuffle xs = do
    let l = length xs
    rands <- take l `fmap` getRandomRs (0, l-1)
    let ar = runSTArray $ do
        ar <- thawSTArray $ listArray (0, l-1) xs
        forM_ (zip [0..(l-1)] rands) $ \(i, j) -> do
            vi <- readSTArray ar i
            vj <- readSTArray ar j
            writeSTArray ar j vi
            writeSTArray ar i vj
        return ar
    return (elems ar)

But this doesn't yield a uniformly-chosen random permutation of its input,
because at the i'th step the first `i` elements are not fixed as they are
in the other algorithms on that page.

Cheers,

David

David Turner

Viktor Dukhovni

Li-yao Xia

tags

participants (3)