P26 - 生成所有 K 元组合

2026-09-07 00:00    #Haskell   #99题   #组合  

P26 - 生成所有 K 元组合

Generate the combinations of K distinct objects chosen from the N elements of a list

官方模块：Problems.P26　核心函数：combinations

← P25 随机排列列表 | P27 互斥分组 →

题目描述

从 nn 个列表元素中选择 kk 个，生成所有组合。组合保留输入顺序，不把同一批元素的不同排列重复计数。

函数签名

1combinations :: Int -> [a] -> [[a]]

实现

方法一：递归回溯

1combinations :: Int -> [a] -> [[a]]
2combinations 0 _      = [[]]
3combinations k _ | k < 0 = []
4combinations _ []     = []
5combinations k (x:xs) =
6  combinations k xs ++ map (x :) (combinations (k - 1) xs)

面对首元素 x，每个组合只有两类：

  1. 不选 x：从 xs 中选 kk 个
  2. 选 x：从 xs 中选 k−1k-1 个，然后 x 放在最前面

这正是二项式恒等式 (nk)=(n−1k)+(n−1k−1)\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} 的程序版本。

方法二：列表推导

1combinations :: Int -> [a] -> [[a]]
2combinations 0 _      = [[]]
3combinations k xs
4  | k < 0     = []
5  | otherwise = [x : ys | x:zxs <- tails' xs, ys <- combinations (k - 1) zxs]
6
7tails' :: [a] -> [[a]]
8tails' [] = [[]]
9tails' xs = xs : tails' (tail xs)

用 tails' 枚举每个元素作为组合的第一个元素，递归取剩下 k−1k-1 个。

方法二详解

核心是这一句：

1[x : ys | x:zxs <- tails' xs, ys <- combinations (k - 1) zxs]

1. tails' 做什么

1tails' "abc"
2-- ["abc", "bc", "c", []]

从每个位置截取「还剩的后缀」。最后一个 [] 会被后面的模式匹配丢掉。

2. 模式 x:zxs <- tails' xs

对每个非空后缀，拆成：

对 "abc"：

后缀xzxs
"abc"'a'"bc"
"bc"'b'"c"
"c"'c'""

也就是说：x 依次当「当前组合的第一个元素」，且后面只能从 zxs 里选——这样就不会重复、也不会打乱相对顺序。

3. 整句在干什么

固定 x 当头后，从 zxs 里再选 k−1k-1 个：

1ys <- combinations (k - 1) zxs

得到 ys，再拼上 x : ys。

4. 例子：combinations 2 "abc"

 1k=2, xs="abc"
 2
 3从 "abc": x='a', zxs="bc"
 4  combinations 1 "bc" = ["b","c"]
 5  → "ab", "ac"
 6
 7从 "bc":  x='b', zxs="c"
 8  combinations 1 "c"  = ["c"]
 9  → "bc"
10
11从 "c":   x='c', zxs=""
12  combinations 1 ""   = []
13  → 无
14
15结果: ["ab","ac","bc"]

5. 和「选 / 不选」写法的关系

写法思路
方法一对首元素：不选 / 选
方法二枚举「谁当组合的第一个元素」，再从它后面选剩下的

方法二用 tails' 保证：一旦选了 x，后面只能从更右边的元素里选，所以每个组合只出现一次。

6. 边界

方法三：使用 subsequences（标准库）

1import Data.List (subsequences)
2
3combinations :: Int -> [a] -> [[a]]
4combinations k xs = filter (\ys -> length ys == k) (subsequences xs)

subsequences 生成所有子序列（子集），然后只保留长度为 kk 的。代码极简，但效率低——生成了 2n2^n 个候选再过滤，K 接近 n/2 时尤其浪费。

方法四：C++ 对照实现

把方法一的递归结构直接翻译成 C++：

 1vector<vector<int>> combinations(int k, const vector<int>& xs) {
 2    if (k == 0) return {{}};          // combinations 0 _ = [[]]
 3    if (k < 0)  return {};            // combinations k _ | k < 0 = []
 4    if (xs.empty()) return {};        // combinations _ [] = []
 5
 6    // 不选 xs[0]
 7    auto rest = vector<int>(xs.begin() + 1, xs.end());
 8    auto without = combinations(k, rest);
 9
10    // 选 xs[0]
11    auto with = combinations(k - 1, rest);
12    for (auto& c : with)
13        c.insert(c.begin(), xs[0]);   // map (x :)
14
15    without.insert(without.end(), with.begin(), with.end());
16    return without;
17}
HaskellC++
[[]]{{}}
[]{}
combinations k xs不选当前元素
map (x :) (combinations (k-1) xs)选当前元素，插到每个组合前面

更常见的迭代写法（DFS 回溯）：

 1vector<vector<int>> combinations(int k, const vector<int>& xs) {
 2    vector<vector<int>> res;
 3    vector<int> path;
 4    function<void(int)> dfs = [&](int start) {
 5        if ((int)path.size() == k) {
 6            res.push_back(path);
 7            return;
 8        }
 9        for (int i = start; i < (int)xs.size(); i++) {
10            path.push_back(xs[i]);
11            dfs(i + 1);
12            path.pop_back();
13        }
14    };
15    dfs(0);
16    return res;
17}

方法对比

方法效率特点
递归回溯O(C(n,k))，只生成需要的组合标准写法，推荐
列表推导 + tailsO(C(n,k))另一种回溯思路
subsequences 过滤O(2ⁿ)，生成了大量多余组合代码短，适合小规模
C++ 递归 / DFSO(C(n,k))对照理解，竞赛常用

测试

1>>> combinations 2 "abcd"
2["cd","bd","bc","ad","ac","ab"]
3>>> length (combinations 3 [1..12])
4220
5>>> combinations 0 [1,2,3]
6[[]]
7>>> combinations 4 [1,2,3]
8[]

参考