递归实现组合型枚举
从 $1∼n$ 这 $n$ 个整数中随机选取 $m$ 个，输出所有可能的选择方案。
输入格式
两个整数 $n, m$
输出格式
按照从小到大的顺序输出所有方案，每行 $1$ 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
数据范围
$n>0$
$0≤m≤n$
$n+(n−m)≤25$
输入样例：
输出样例：
1
2
3
4
5
6
7
8
9
10
| 1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
|
思考题：如果要求使用非递归方法，该怎么做呢？
解析
上一道题的另外一个版本，用 dfs 同理，这次存进 $m$ 个就跳出循环即可，本题的另一个问题是使用非递归的方法。
正好把我们的位运算继续拿出来继续用， $m$ 个数的条件好说，但是这次需要根据字典序排序，再用上次的方法就不行了（这里思考为什么不行？提供代码）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <cstdio>
#include <iostream>
int n, m;
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < 1 << n; i++) {
int tot = 0;
for (int j = 0; j < n; j++) {
if(i >> j & 1) tot++;
} if(tot == m) {
for (int j = 0; j < n; j++) {
if(i >> j & 1) printf("%d ", j + 1);
} printf("\n");
}
} return 0;
}
|
既然要排序，那我们用结构体储存了之后再用 sort 的排序即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <cstdio>
#include <iostream>
#include <algorithm>
int n, m, tot, tnt;
const int N = 100005;
struct point {
std::vector<int> v1;
} arr[N];
bool cmp(point a, point b) {
int equal = 0;
while(a.v1[equal] == b.v1[equal]) equal++;
return a.v1[equal] < b.v1[equal];
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < 1 << n; i++) {
int tot = 0;
for (int j = 0; j < n; j++) {
if(i >> j & 1) tot++;
} if(tot == m) {
for (int j = 0; j < n; j++) {
if(i >> j & 1) arr[tnt].v1.push_back(j + 1);
} tnt++;
}
}
std::sort(arr, arr + tnt, cmp);
for (int i = 0; i < tnt; i++) {
for (int j = 0; j < m; j++) {
printf("%d ", arr[i].v1[j]);
} puts("");
}
return 0;
}
|
此处在书前还有一个 $lowbit$ 的详细用法，我们再使用 $lowbit$ 解决这道题
$lowbit$ 的定义是非负整数 n 在二进制表示下 “最低位的 1 及其后边所有的 0”构成的数值，所以我们插入使用一下即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <cstdio>
#include <iostream>
#include <algorithm>
int n, m, tot, tnt;
const int N = 100005;
struct point {
std::vector<int> v1;
} arr[N];
int lowbit(int x) {
return x & (-x);
}
bool cmp(point a, point b) {
int equal = 0;
while(a.v1[equal] == b.v1[equal]) equal++;
return a.v1[equal] < b.v1[equal];
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < 1 << n; i++) {
int tot = 0, val = i;
while(val) { val -= lowbit(val); tot++; }
if(tot == m) {
for (int j = 0; j < n; j++) {
if(i >> j & 1) arr[tnt].v1.push_back(j + 1);
} tnt++;
}
}
std::sort(arr, arr + tnt, cmp);
for (int i = 0; i < tnt; i++) {
for (int j = 0; j < m; j++) {
printf("%d ", arr[i].v1[j]);
} puts("");
}
return 0;
}
|