DFS算法 全排列问题

DFS算法

俗称 不撞南墙不回头算法 一条路走到黑

废话少说 直接上代码 

这是一道例题 关于全排列 在n个数中 选三个数进行排列 看有多少种结果

#include<iostream>

using namespace std;

/// <summary>
/// 不撞南墙不回头系列 一条路走到黑 然后回溯 改变路径(改变某个位置的数 继续往下排)
//</summary>

int n, s, ans; // n个数 选r个进行全排列 一共ans个全排列
int mark[510]; // 标记 r个位置中 莫个数是否被使用 
int resreve[510]; // 用来储存排列结果

void dfs(int cur) { //cur 表示当前位置 - 1
	if (cur == s + 1) { // 到了第四个位置 那么 就应该打印了 不应该储存了
		for (int i = 1; i <= s; i++) {
			cout << resreve[i];
		}
		cout << "\n";
		ans++;
		return; // 不能继续往下走了  已经到了三个数了(已经撞墙了) 开始回溯 
	}

	for (int i = 1; i <= n; i++) {
		if (!mark[i]) { // 表示这个新排序中 这个位置 这个数还没用过
			mark[i] = 1; // 标记当前排序中 这个位置 这个数用过了
			resreve[cur] = i; // 让当前位置 等于没用过的那个数
			dfs(cur + 1); // 开始排下一个位置的数
			mark[i] = 0;
			// 要进行新的排序了 那么 这个位置的这个数 不可能再被用了 
			// 而且进行了下一个循环 要新排序了 所以这个数 应该重置
			// 每经历一个新的for循环 就相当于 要产生新排序了 这个数要被重新利用了 所以要把它重置
		}
	}
}

int main(void) {
	cin >> n >> s;

	dfs(1); // 从第一个位置 开始设置数

	cout << ans;

	return 0;
}

运行结果如下图所示 非常的简单是不是 哈哈  

4 3
123
124
132
134
142
143
213
214
231
234
241
243
312
314
321
324
341
342
412
413
421
423
431
432
24

还有更简单的 来看 我们通过一个函数进行全排列 但是 有弊端 需要我们自己找出 所有的数字组合

代码如下 

#include<iostream>
#include<algorithm>

using namespace std;

/// <summary>
/// next_permutation 函数会自动给我们进行全排列
/// </summary>
/// <param name=""></param>
/// <returns></returns>

int main(void) {
	int ans = 0;

	int num1[3] = { 2,1,3 };
	int num2[3] = { 3,1,4 };
	int num3[3] = { 3,2,4 };
	int num4[3] = { 1,2,4 };

	sort(num1,num1 + 3);
	sort(num2,num2 + 3);
	sort(num3,num3 + 3); // 要用下面的方法 必须是升序 数组
	sort(num4, num4+ 3);

	do {
		ans++;
		for (int i = 0; i < 3; i++)
		{
			cout << num1[i];
		}
		cout << "\n";
	} while (next_permutation(num1, num1 + 3));

	do {
		ans++;
		for (int i = 0; i < 3; i++)
		{
			cout << num2[i];
		}
		cout << "\n";
	} while (next_permutation(num2, num2 + 3));

	do {
		ans++;
		for (int i = 0; i < 3; i++)
		{
			cout << num3[i];
		}
		cout << "\n";
	} while (next_permutation(num3, num3 + 3));

	do {
		ans++;
		for (int i = 0; i < 3; i++)
		{
			cout << num4[i];
		}
		cout << "\n";
	} while (next_permutation(num4, num4 + 3));

	cout << ans;

	return 0;
}

运行结果如下

123
132
213
231
312
321
134
143
314
341
413
431
234
243
324
342
423
432
124
142
214
241
412
421
24

OK了 关于全排列 相信大家已经完全理解了