P24 - 从 1..M 中随机选 N 个不同数

2026-09-07 00:00    #Haskell   #99题   #列表  

P24 - 从 1..M 中随机选 N 个不同数

Draw N different numbers from the set {1 .. M}

官方模块：Problems.P24　核心函数：randomDraw

← P23 从列表随机选 N 个元素 | P25 随机排列列表 →

题目描述

从 11 到 MM 的整数中随机选出 NN 个不同的数。这是 P23 的直接应用——把 [1..M] 作为候选列表。

函数签名

1import System.Random (RandomGen)
2
3randomDraw :: RandomGen g => Int -> Int -> g -> ([Int], g)

参数顺序：randomDraw n m gen（选 N 个，范围 1..M）。

实现

方法一：基于 randomSelect

1import System.Random (RandomGen)
2
3randomDraw :: RandomGen g => Int -> Int -> g -> ([Int], g)
4randomDraw n m = randomSelect [1 .. max 0 m] n

如果 M ≤ 0，[1 .. max 0 m] 得到 []，randomSelect 返回空列表。一行搞定。

方法二：直接实现——抽取不放回

 1import System.Random (RandomGen, randomR)
 2
 3randomDraw :: RandomGen g => Int -> Int -> g -> ([Int], g)
 4randomDraw n m gen = go count [1 .. max 0 m] gen []
 5  where
 6    count = max 0 (min n m)
 7    go 0 _     g acc = (acc, g)
 8    go _ []    g acc = (acc, g)
 9    go k pool g acc =
10      let (i, g') = randomR (0, length pool - 1) g
11          x       = pool !! i
12          pool'   = take i pool ++ drop (i + 1) pool
13      in go (k - 1) pool' g' (x : acc)

不依赖 randomSelect，从数组中用下标随机取元素并移除，逻辑自包含。

方法三：——洗牌后取前 N 个

 1import System.Random (RandomGen, randomR)
 2
 3randomDraw :: RandomGen g => Int -> Int -> g -> ([Int], g)
 4randomDraw n m gen = (take (max 0 (min n m)) shuffled, gen')
 5  where
 6    (shuffled, gen') = shuffle [1 .. max 0 m] gen
 7
 8shuffle :: RandomGen g => [a] -> g -> ([a], g)
 9shuffle [] g = ([], g)
10shuffle xs g = go (length xs) xs g
11  where
12    go 0 acc g = (acc, g)
13    go len acc g =
14      let (i, g') = randomR (0, len - 1) g
15          swapped = swap i (len - 1) acc
16      in go (len - 1) swapped g'
17
18swap :: Int -> Int -> [a] -> [a]
19swap i j xs
20  | i == j    = xs
21  | otherwise =
22      [if k == i then xj else if k == j then xi else x
23      | (k, x) <- zip [0..] xs]
24  where
25    xi = xs !! i
26    xj = xs !! j

Fisher-Yates 洗牌后取前 N 个，适合 M 不大且需要多次抽样的场景。

方法对比

方法代码量依赖特点
randomSelect 代理1 行P23复用已有代码
直接抽取≈10 行无算法自包含
洗牌 + 取前 N≈12 行无M 较小时效率最高

测试

1>>> import Data.List (nub)
2>>> import System.Random (mkStdGen)
3>>> let (xs, _) = randomDraw 6 49 (mkStdGen 111)
4>>> length xs == 6
5True
6>>> length (nub xs) == 6 && all (`elem` [1..49]) xs
7True
8>>> length . fst $ randomDraw 20 5 (mkStdGen 1)   -- N > M 时只返回 5 个
95

参考