洛谷P1076全排列问题题解

题目

题目描述

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

输入格式
一个整数 n。

输出格式

由 1~n 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5 个场宽。

输入输出样例

输入
3
输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路分析

诈一看，这是一道全排列问题 。但我们可以用深搜的方法解决。

---

以下是百度百科上关于全排列的定义（原文链接点这里）：

从n个不同元素中任取m（m<=n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

现在观察样例，发现查找的顺序因该是由小到大。

完整AC代码

#include<iostream>
using namespace std;
int vst[10],n,result[20]; //vst是标记是否使用过该数字，n是输入，result存储结果
void print(){ //单独的输出函数
	for(int i=1;i<=n;i++){ //输出n个数的全排列结果
		cout<<"    "<<result[i];
	}
	cout<<endl;
}
void dfs(int num){ //【此注释一定要看】num代表的是现在正在排列第n位数
	if(num==n+1){ //为什么要n+1？在第n次的时候，还在排列最后一位数。只有n+1时，才是排列结束的结果
		print();
		return;
	}
	for(int i=1;i<=n;i++){ //分别尝试范围内的数是否满足条件
		if(vst[i]==0){ //需判断的条件：数字没有被使用过
			result[num]=i; //存储排列结果
			vst[i]=1; //标记此数字已使用
			dfs(num+1); //dfs深搜
			vst[i]=0; //标记此数字未使用
		}
	}
}
int main(){ //main没有必要解释。。。
	cin>>n;
	dfs(1);
	return 0;
}

推荐阅读

1.洛谷P2108学英语题解，点击查看
2.洛谷P1076寻宝题解，点击查看

拓展

如果把样例改成这样呢？

输入
3
输出
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3

这里只写出最核心部分：

+for(int i=1;i<=n;i++){
-for(int i=n;i>=1;i--){
	if(vst[i]==0){
		result[num]=i;
		vst[i]=1;
		dfs(num+1);
		vst[i]=0;
	}
 }