递归实现组合型枚举
从 $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; }
|