递归实现组合型枚举

递归实现组合型枚举

从 $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
5 3

输出样例:

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;
}