P25 - 随机排列列表
Generate a random permutation of the elements of a list
官方模块：
Problems.P25核心函数：randomPermute
← P24 从 1..M 中随机选 N 个不同数 | P26 生成所有 K 元组合 →
题目描述
随机排列列表中的元素（Fisher-Yates 洗牌算法）。输入列表的所有元素必须出现在输出中，且每种排列等概率。
函数签名
1import System.Random (RandomGen)
2
3randomPermute :: RandomGen g => [a] -> g -> ([a], g)
实现
方法一：基于 randomSelect
1import System.Random (RandomGen)
2
3randomPermute :: RandomGen g => [a] -> g -> ([a], g)
4randomPermute xs = randomSelect xs (length xs)
随机选 length xs 个元素，每次从剩余池中抽取不放回，结果恰好是原列表的一个随机排列。利用 P23 一行搞定。
方法二：Fisher-Yates 洗牌
1import System.Random (RandomGen, randomR)
2
3randomPermute :: RandomGen g => [a] -> g -> ([a], g)
4randomPermute xs gen = go (length xs) xs gen
5 where
6 go 0 acc gen = (acc, gen)
7 go n acc gen =
8 let (i, gen') = randomR (0, n - 1) gen
9 swapped = swap i (n - 1) acc
10 in go (n - 1) swapped gen'
11
12swap :: Int -> Int -> [a] -> [a]
13swap i j xs
14 | i == j = xs
15 | otherwise =
16 [if k == i then xj else if k == j then xi else x
17 | (k, x) <- zip [0..] xs]
18 where
19 xi = xs !! i
20 xj = xs !! j
经典的 Fisher-Yates 算法，从后往前遍历，每步随机选一个未处理的元素与当前位置交换。
方法三：逐个插入
1import System.Random (RandomGen, randomR)
2
3randomPermute :: RandomGen g => [a] -> g -> ([a], g)
4randomPermute [] gen = ([], gen)
5randomPermute (x:xs) gen =
6 let (permuted, gen') = randomPermute xs gen
7 (pos, gen'') = randomR (0, length permuted) gen'
8 (front, back) = splitAt pos permuted
9 in (front ++ x : back, gen'')
递归：先随机排列尾部，再随机将头元素插入结果中任意位置。思考过程更符合"分治"直觉，但效率不如 Fisher-Yates。
Fisher-Yates 直观理解
1初始: [a, b, c, d, e]
2
3Step 1: 随机 i ∈ [0..4], 假设 i=2 → 交换位置 2 和 4 → [a, b, e, d, c]
4Step 2: 随机 i ∈ [0..3], 假设 i=0 → 交换位置 0 和 3 → [d, b, e, a, c]
5Step 3: 随机 i ∈ [0..2], 假设 i=1 → 交换位置 1 和 2 → [d, e, b, a, c]
6Step 4: 随机 i ∈ [0..1], 假设 i=1 → 交换位置 1 和 1 → [d, e, b, a, c]
7结束: [d, e, b, a, c]
测试
1>>> import Data.List (sort)
2>>> import System.Random (mkStdGen)
3>>> let (ys, _) = randomPermute [1..10] (mkStdGen 111)
4>>> sort ys == [1..10]
5True
6>>> fst (randomPermute [] (mkStdGen 1))
7[]
8>>> sort (fst (randomPermute "aab" (mkStdGen 2)))
9"aab"