Fisher–Yates shuffle 算法

Fisher–Yates shuffle算法是一个经典的随机洗牌算法，而且非常简洁。

自己用Haskell实现了一个:

module Shuffle where

import System.Random
import Data.Array
import Data.List (mapAccumL)

shuffle :: StdGen -> Array Int a -> Array Int a
shuffle stdgen arr = foldl swap arr swaps
  where
    (l, r) = bounds arr
    swaps  = snd $ mapAccumL go stdgen [r, r - 1 .. l + 1]
    go g i = let (j, g') = randomR (l, i) g in (g' , (i, j))

swap :: Ix i => Array i e -> (i, i) -> Array i e
swap arr (i, j) =
    let ai = arr ! i
        aj = arr ! j
    in arr // [(i, aj), (j, ai)]

先生成交换序列，然后交换。

为什么一定要从后往前排呢, 用 [l + 1 .. r], 递增不是更好吗? (随机数的范围要改成(i, r))。 我觉得多半是因为 while (i--)要比 while (i++ < r)和for循环要好看, 而且性能一样(如果INC和DEC一样, 所有条件跳转一样)。

测试的时候发现Hugs经常出这个错误:Program error: undefined array element，GHC倒没出现过问题。 然后看了好久好久，确定没有越界啊，用Debug.Trace.trace才发现，GHC和Hugs的生成随机数是一样的，但是Hugs会在原地交换的时候就会出错。 更准确的说，Hugs的//一次不能修改同一下标的值多次。

Main> array (0,0) [(0,0)] // [(0,0), (0,1::Int)]
array (0,0) [(0,
Program error: undefined array element

Main> array (0,0) [(0,0)] // [(0,1::Int)]
array (0,0) [(0,1)]

Main> array (0,0) [(0,0)] // [(0,0)] // [(0, 1::Int)]
array (0,0) [(0,1)]