搜索入门——全排列问题

1.问题描述：

2.算法分析：

这道题目其实是搜索入门的一道题搜索，可以使用dfs来搜索，怎么搜索呢，首先我们输入一个n，这个n代表全排列1-n，使用dfs搜索的话，我们要确定边界出口，我们是一步一步去试，每一次次数step + 1，当step比n大的时候就跳出递归，但是我们需要多次搜索，所以需要在选数的时候添加一个记录这个数选与没选的vis标记数组，其实dfs是有模板的，如下：

void dfs(int step)
{
	判断边界
	尝试每一种可能for (int i = 1; i <= n; i++)
	{
		继续下一步dfs(step + 1);
	}
	返回
}

这道题目还可以有一个巧解熟悉C++的一个algorithm的next_permutation
模板如下：

3.源代码：

先贴一份dfs的代码：

#include <iostream>
#include <cstdio>
using namespace std;

int a[10],n; 
bool vis[10];

void dfs(int step) {
	if (step == n + 1) {
		for (int i = 1; i <= n; i++) {
			printf("%5d",a[i]);
		}
		printf("\n");
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			a[step] = i;
			vis[i] = true;
			dfs(step + 1);
			vis[i] = false;
		}
	}
}

int main() {
	scanf("%d",&n);
	dfs(1);
	return 0;
}

std巧解代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int a[9];

int main() {
	int n;
	scanf("%d",&n);
	for (int i = 0; i < n; i++) {
		a[i] = i + 1;
	}
	do {
		for (int i = 0; i < n; i++) {
			printf("%5d",a[i]);
		}
		printf("\n");
	} while (next_permutation(a,a + n));
	return 0;
}

欢迎关注www.lyxueit.com。一起学习算法。
测试地点落谷：
https://www.luogu.org/problemnew/show/P1706