全组合算法（Full Combination）

定义#

从含 $n$ 个元素的集合 $A = \{a_1, \cdots, a_n\}$ 中任取 $m$ （ $0 \leq m \leq n$ ）个元素，组成的子集称为组合（Combination）。当 $m < n$ 时，组合数为

C_n^m = \binom{n}{m} = \frac{n!}{m!(n-m)!}.

给定集合 $A$ 和 $m$ 时，所有可能的组合构成的集合称为全组合（Full Combination）。全组合的实现同样可分递归（回溯）与非递归。下文默认集合元素为 $0, \cdots, N-1$ （与代码一致）；若要使用 $1, \cdots, N$ ，初始化时改为 a[i] = i + 1 即可。

递归实现#

1. 递归回溯法#

由组合恒等式出发

C_n^m = C_{n-1}^m + C_{n-1}^{m-1}

可把从 $n$ 个元素中取 $m$ 个元素拆解成一系列与单一元素 $a_i$ 相关的两个子问题：

不选 $a_i$ ：在剩余 $n-1$ 个中取 $m$ 个 $\Rightarrow C_{n-1}^m$ ；
选 $a_i$ ：在剩余 $n-1$ 个中再取 $m-1$ 个 $\Rightarrow C_{n-1}^{m-1}$ 。

递归边界：已取满 $m$ 个则输出；下标越界且未取满则失败返回。实现上是回溯：先试探选中当前元素，再试探不选；对应递归调用中，先递归调用不选，再递归调用选。

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
vector<int> res;
6
int N, M;
7
int *a;
8

9
void print() {
10
    for (int i = 0; i < (int)res.size(); ++i) {
11
        cout << res[i] << ' ';
12
    }
13
    cout << endl;
14
}
15

16
// k：当前考虑的下标；m：还需要再取多少个（此处用 res.size() 与 M 判断亦可）
17
void combination(int k, int m) {
18
    if ((int)res.size() == M) {
19
        print();
20
        return;
21
    }
22
    if (k >= N) {
23
        return;
24
    }
25
    res.push_back(a[k]);
26
    combination(k + 1, m - 1); // 选
27
    res.pop_back();
28
    combination(k + 1, m);     // 不选
29
}
30

31
int main() {
32
    cin >> N >> M;
33
    a = new int[N];
34
    for (int i = 0; i < N; ++i) {
35
        a[i] = i;
36
    }
37
    combination(0, M);
38
    delete[] a;
39
    return 0;
40
}

2. 顺序法（递归）#

更常见的写法：强制按递增下标选取，避免同一子集因顺序不同被重复枚举。先取第 $1$ 个元素可选范围为下标 $[0, N-M]$ ，再递归取后续；当还剩 $1$ 个名额时，遍历剩余元素并输出。

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
vector<int> res;
6
int N, M;
7
int *a;
8

9
void print() {
10
    for (int i = 0; i < (int)res.size(); ++i) {
11
        cout << res[i] << ' ';
12
    }
13
    cout << endl;
14
}
15

16
void combination(int k, int m) {
17
    if (m == 1) {
18
        for (int i = k; i < N; ++i) {
19
            res.push_back(a[i]);
20
            print();
21
            res.pop_back();
22
        }
23
        return;
24
    }
25
    for (int i = k; i <= N - m; ++i) {
26
        res.push_back(a[i]);
27
        combination(i + 1, m - 1);
28
        res.pop_back();
29
    }
30
}
31

32
int main() {
33
    cin >> N >> M;
34
    a = new int[N];
35
    for (int i = 0; i < N; ++i) {
36
        a[i] = i;
37
    }
38
    combination(0, M);
39
    delete[] a;
40
    return 0;
41
}

非递归实现#

3. 顺序法（嵌套循环）#

用 $m$ 层循环，每层选一个严格递增的下标。与全排列里的蛮力法一样：层数绑死 $m$ ，改 $m$ 就要改代码。

以 $m = 3$ 为例：

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
vector<int> res;
6
int N;
7
int M = 3;
8
int *a;
9

10
void print() {
11
    for (int i = 0; i < (int)res.size(); ++i) {
12
        cout << res[i] << ' ';
13
    }
14
    cout << endl;
15
}
16

17
int main() {
18
    cin >> N;
19
    a = new int[N];
20
    for (int i = 0; i < N; ++i) {
21
        a[i] = i;
22
    }
23
    for (int i1 = 0; i1 < N - 2; ++i1) {
24
        res.push_back(a[i1]);
25
        for (int i2 = i1 + 1; i2 < N - 1; ++i2) {
26
            res.push_back(a[i2]);
27
            for (int i3 = i2 + 1; i3 < N; ++i3) {
28
                res.push_back(a[i3]);
29
                print();
30
                res.pop_back();
31
            }
32
            res.pop_back();
33
        }
34
        res.pop_back();
35
    }
36
    delete[] a;
37
    return 0;
38
}

4. 状态序列 + 全排列#

对于每个元素 $a_i$ ，只有在与不在子集中两种状态。可构造长度为 $n$ 、恰含 $m$ 个 1 与 $n-m$ 个 0 的状态串 $C$ ， $C$ 的每一种不同排列对应一种组合。那么问题就转换为了求 $C$ 的互异全排列问题。

例： $A=\{1,2,3,4\}$ ， $m=2$ ，初始 $C=\{1,1,0,0\}$ ，用字典序/反字典序枚举 $C$ 的互异排列：

状态 $C$	取出的元素
$1,1,0,0$	$1,2$
$1,0,1,0$	$1,3$
$1,0,0,1$	$1,4$
$0,1,1,0$	$2,3$
$0,1,0,1$	$2,4$
$0,0,1,1$	$3,4$

全排列算法见全排列一文。非递归时可用 prev_permutation / next_permutation 枚举状态串：

1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
#include <string>
5
using namespace std;
6

7
vector<int> res;
8
int N, M;
9
int *a;
10
string b;
11

12
void print() {
13
    for (int i = 0; i < (int)res.size(); ++i) {
14
        cout << res[i] << ' ';
15
    }
16
    cout << endl;
17
}
18

19
int main() {
20
    cin >> N >> M;
21
    a = new int[N];
22
    b.append(M, '1').append(N - M, '0');
23
    for (int i = 0; i < N; ++i) {
24
        a[i] = i;
25
    }
26
    do {
27
        for (int i = 0; i < N; ++i) {
28
            if (b[i] == '1') {
29
                res.push_back(a[i]);
30
            }
31
        }
32
        print();
33
        res.clear();
34
    } while (prev_permutation(b.begin(), b.end()));
35
    delete[] a;
36
    return 0;
37
}

提示

next_permutation / prev_permutation 在有重复元素时只会生成互异排列，因此对 $m$ 个 $1$ 、 $n-m$ 个 $0$ 的串，枚举次数是 $C_n^m$ 而非 $n!$ 。

音乐

音乐

定义#