关于排列与组合的枚举

Posted on | In | | Visitors:
Words count in article: 1.3k

关于排列与组合的枚举

最近刷题的时候碰到了这两种题型，主要就是计算排列数和组合数，自己做了之后看了一些解题发现帮助挺大的，做一个小笔记~

1.组合的枚举

洛谷P1157 组合的输出

组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r ≤ n )，我们可以简单地将n个元素理解为自然数1, 2, …, n，从中任取 r 个数。

举个栗子：例如 n = 5, r = 3，则所有的组合为：123, 124, 125, 145, 234, 235, 245, 345

解法一：这题最容易想到的就是dfs，递归求解，搜索与回溯，比较简单，直接上代码：

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
// 洛谷P1157 组合的输出
#include<iostream>
using namespace std;
int n, r, num[22];
void func(int index, int start) {
	if (index == r - 1) {		// 已经取满r个时输出
		for (; start <= n; start++) {
			for (int i = 0; i < r - 1; i++) {
				printf("%3d", num[i]);
				//cout << num[i] << " ";
			}
			printf("%3d\n", start);
			//cout << start << endl;
		}
	}
	else if(index < r - 1){		// 不满r个时继续递归
		while (start <= n - r + index + 1) {
			num[index] = start;
			++start;
			func(index + 1, start);		// 递归求解后回溯
		}
	}
}
int main()
{
	cin >> n >> r;
	func(0, 1);
	return 0;
}

解法二：上面的递归解法虽然容易想到，但是存在一定的问题，就是当 r 比较大时， 递归的深度就会非常深，有可能就会导致程序无法运行，所以非递归解法就十分有必要了

主要存在四个分支（以输入为 m = 5, r = 3 为例）：

  1. 已经填满 r 个：直接输出结果，例如 index = 4, num = [1, 2, 3]
  2. 当未填满且当前位为 0 时：将当前为赋值为前一位加一，例如 index = 3 , num = [1, 2, 0] -> [1, 2, 3]
  3. 当未填满且当前位不为0时：判断当前位是否能过加一（不超出 n 的范围，例如： index = 3 , num = [1, 2, 3] -> [1, 2, 4]
  4. 如果都不满足上述情况就向前回溯一位，并将当前位置为0，例如：index = 3, num = [1, 2, 5] -> index = 2, num= [1, 2, 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
// 洛谷P1157 组合的输出
#include<iostream>
#include<string.h>
using namespace std;
int main() {
	int n, r, num[22], index = 1;
	memset(num, 0, 22 * sizeof(int));
	scanf("%d%d", &n, &r);
	while (index > 0) {
		if (index >= r + 1) {		// 当填满时，输出
			for (int i = 1; i <= r; i++) {
				printf("%3d", num[i]);
			}
			printf("\n");
			index--;		// 回溯到前一位
			continue;
		}
		if (num[index] == 0) {		// 当该位为0时，赋值为前一位加1
			num[index] = num[index - 1] + 1;
			index++;
			continue;
		}
		if (num[index] < n - r + index) {	// 核心步骤：判断当前位是否还能递增
			num[index]++;
			index++;
			continue;
		}
		num[index] = 0;		//  如果上述条件都不满足，则向前回溯
		index--;
	}
	return 0;
}

2.排序的枚举

洛谷P1706 全排列问题

洛谷P1088 火星人

输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

举个栗子：例如 n = 3，则所有的组合为：123, 132, 213, 231, 312, 321

说在前面，可能C/C++选手会说直接next_permutation就可以了，但是这里不考虑这种方法了，重在开拓思路！

解法一：同样的思路，也可以使用dfs深度搜索枚举出所有的情况，思路也非常的简单，代码易懂：

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
// 洛谷P1706 全排列问题
#include<iostream>
#include<algorithm>
int num[10], tag[10] = { 0 }, n;
using namespace std;
void dfs(int index) {
	if (index == n) {
		for (int i = 0; i < n; i++) {
			printf("%5d", num[i]);
		}
		printf("\n");
	}
	for (int i = 0; i < n; i++) {
		if (tag[i] == 0) {
			num[index] = i + 1;
			tag[i] = 1;
			dfs(index + 1);
			tag[i] = 0;
		}
	}
}
int main() {
	scanf("%d", &n);
	dfs(0);
	return 0;
}

解法二：同样的，上述递归解法也是存在如果n过大，递归层数就会过深，可能引起程序奔溃，比如上述提到的洛谷P1088 火星人，n 甚至回达到 10000 这个数量级，然后上述递归解法就崩溃了，所以就需要非递归解法。

非递归解法其实也非常的自然，就是模拟我们计算下一个排序数时的思路，我大概举了一个小栗子，需要可以参考一下：

0AeYRI.png

然后就是代码实现了，其实就是严格按照上面思路些代码就好了~

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
#include<iostream>
#include<algorithm>
int num[11000];
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	int m, n, j, k;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	for (int i = 0; i < m; i++) {
		j = n - 2;
		while (num[j + 1] < num[j]) { // 1.从最后一位开始，找到第一个可增加的数
			j--;
		}
		k = n - 1;
		while (num[k] < num[j]) {	// 2.在该可增加的数之后找到一个比它大的数
			k--;
		}
		swap(num[j], num[k]);	// 3.然后交换两数的位置
		j++;
		k = n - 1;
		while (j < k) {		// 4.然后将两数之间的数进行位置互换（其实就是排序）
			swap(num[j], num[k]);
			j++;
			k--;
		}
	}
	for (int i = 0; i < n - 1; i++) {
		cout << num[i] << " ";
	}
	cout << num[n - 1] << endl;
	return 0;
}