[Haskell-cafe] Bug in random shuffle algorithm

Viktor Dukhovni ietf-dane at dukhovni.org
Tue May 9 05:46:52 UTC 2017

> On May 8, 2017, at 12:02 PM, David Turner <dct25-561bs at mythic-beasts.com> wrote:
> 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.

Channeling Samuel Dukhovni, who provided a patch for the same bug in
older versions of Postfix a few years back, his suggested patch is:

 shuffle :: RandomGen g => [a] -> Rand g [a]
 shuffle xs = do
     let l = length xs
-     rands <- take l `fmap` getRandomRs (0, l-1)
+     rands <- forM [0..(l-1)] (\i -> getRandomR (i, 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)

Perhaps someone can forward this along to the package maintainer.

Also as an optimization, the `rands` list should be made one element
shorter, and likewise the `zip [0..(l-1)]` should become `zip [0..(l-2)]`.
The reason is of course that by the time we only have one final element
left there's nothing left to permute.


P.S.  The corresponding new Postfix code can be found at


     * Shuffle resource records. Every element has an equal chance of landing
     * in slot 0.  After that every remaining element has an equal chance of
     * landing in slot 1, ...  This is exactly n! states for n! permutations.
    for (i = 0; i < len - 1; i++) {
        r = i + (myrand() % (len - i));         /* Victor&Son */
        rr = rr_array[i];
        rr_array[i] = rr_array[r];
        rr_array[r] = rr;

More information about the Haskell-Cafe mailing list