haskell枚举

在 Codeforces 等竞技编程（CP）中，Haskell 的优势在于惰性求值（Lazy Evaluation）和列表推导（List Comprehension）。你可以定义一个巨大的搜索空间（比如全排列），然后只取前几个符合条件的解，而不需要真正生成所有数据。

这是一份针对 Haskell 选手的枚举算法 Cheatsheet。

0. 核心引入 (The Essentials)

几乎所有的枚举与列表操作都需要 Data.List，涉及重复生成的往往需要 Control.Monad。

1import Data.List
2import Control.Monad (replicateM, forM_)

1. 全排列 (Permutations)

标准全排列

Data.List.permutations 是最直接的工具。注意：生成的顺序不是严格字典序。

1-- 用法
2perms :: [[Int]]
3perms = permutations [1, 2, 3]
4-- 输出: [[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]

字典序全排列 (Lexicographical Order)

如果题目要求按字典序输出，你需要先排序（如果 $N$ 较小，比如 $N \le 10$ ）：

1sortedPerms = sort $ permutations [1, 2, 3]

CP 技巧： 如果需要在 $N$ 稍大时寻找特定排列，使用 permutations 可能会 TLE。对于简单的枚举检查，配合惰性求值使用 find： result = find checkCondition (permutations xs)

2. 组合 (Combinations) $C(n, k)$

Haskell 标准库没有直接的 combinations 函数，通常使用以下两种方式：

方法 A：利用 `subsequences` (数据量极小)

subsequences 生成幂集，然后过滤长度。仅适用于 $N$ 很小的情况。

1comb :: Int -> [a] -> [[a]]
2comb k xs = filter ((== k) . length) (subsequences xs)

方法 B：递归生成 (标准高效写法)

这是 CP 中最常用的手写 snippet，效率比方法 A 高很多，因为它通过剪枝避免了生成无效长度的子集。

1-- 从 xs 中选 k 个
2combinations :: Int -> [a] -> [[a]]
3combinations 0 _  = [[]]
4combinations _ [] = []
5combinations k (x:xs) = (map (x:) (combinations (k-1) xs)) ++ combinations k xs

3. 全部子序列 / 子集 (Subsequences / Power Set)

生成所有可能的子集（包括空集）。

1subs :: [[Int]]
2subs = subsequences [1, 2, 3]
3-- 输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

注意：

长度为 $N$ 的列表有 $2^N$ 个子序列。
$N=20$ 时约 $10^6$ ，是可以接受的。
$N=25$ 时约 $3 \times 10^7$ ，可能会 TLE。

4. 重复排列 / 笛卡尔积 (Cartesian Product)

这是 Haskell 的杀手锏。用于解决类似：“长度为 N 的二进制串”、“密码破解”、“网格遍历”等问题。

只有两个列表的积 (Pairing)

使用列表推导：

1pairs = [[x, y] | x <- [1..3], y <- [1..3]]

N 个列表的积 (或者从集合 S 中取 N 次)

使用 replicateM (需要 import Control.Monad)。这是生成 $N^K$ 复杂度枚举的神器。

1-- 例子：生成长度为 3 的所有二进制串
2binaryStrings :: [[Int]]
3binaryStrings = replicateM 3 [0, 1]
4-- result: [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
5
6-- 例子：生成 4 位数字密码 (0-9)
7passwords = replicateM 4 [0..9]

5. 连续子段 (Subarrays / Segments)

不同于子序列（可以不连续），子段必须连续。

1-- 获取所有非空连续子段
2segments :: [a] -> [[a]]
3segments xs = [take len (drop i xs) | i <- [0..n-1], len <- [1..n-i]]
4  where n = length xs
5
6-- 或者利用 tails 和 inits (更 Haskell 的写法)
7segments' :: [a] -> [[a]]
8segments' = concatMap (tail . inits) . tails

6. 实战模板：DFS / 回溯 (General Backtracking)

在 Haskell 中，利用 List Monad 写回溯算法非常优雅。列表 Monad 自动处理了“非确定性计算”，本质上就是 DFS。

场景： 八皇后问题，或者更复杂的带状态枚举。

 1-- 这是一个通用的思维模型
 2solve :: State -> [Result]
 3solve state = do
 4    -- 1. 生成下一步所有可能的选择
 5    nextStep <- generateChoices state
 6    
 7    -- 2. 剪枝 (Guard): 如果不满足条件，这就返回 [] (即回溯)
 8    guard (isValid nextStep)
 9    
10    -- 3. 递归或返回结果
11    if isGoal nextStep 
12       then return nextStep 
13       else solve nextStep

简单示例：在列表 [1,2,3] 中选两个数，和为 4

1import Control.Monad (guard)
2
3sols :: [(Int, Int)]
4sols = do
5    x <- [1, 2, 3]
6    y <- [1, 2, 3]
7    guard (x + y == 4)  -- 不满足则自动回溯
8    return (x, y)

总结表格 (Quick Reference)

需求	Haskell 函数 / 方法	复杂度	备注
全排列	`permutations xs`	$O(N!)$	惰性生成，不保序
组合 $C(n,k)$	手写递归 (见上文)	$O(\binom{n}{k})$	推荐手写，`subsequences` 较慢
所有子集	`subsequences xs`	$O(2^N)$	包含空集
重复选取	`replicateM k xs`	$O(	xs
笛卡尔积	`sequence [list1, list2...]`	$O(\Pi	list_i
连续子数组	`tails` + `inits`	$O(N^2)$	需要组合使用

给 Haskell 选手的一个建议

不要滥用 length。在枚举题目中，如果你写 filter (\x -> length x == k) (subsequences xs)，Haskell 会真的去遍历整个子序列列表并计算长度。对于大列表，这会极慢。尽量在生成阶段（如上面的递归版 combinations）就控制长度。