#题解全排列问题

发布于 2020-05-01 | 分类于题解 | 3分钟 | 654字数 | 浏览量：

我们先来读题啊啊啊

题目描述

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

输入格式

一个整数 n。

输出格式

由 $1 \sim n$ 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5 个场宽。

输入输出样例

输入 #1

输出 #1

1    2    3
1    3    2
2    1    3
2    3    1
3    1    2
3    2    1

说明/提示

$1 \leq n \leq 9$

具体实现

要解决这题，就必须用到递归，所谓递归就是不断将问题规模缩小，直至某个答案显而易见的终点。
这一题可以利用循环和递归一起，从样例3中来分析，第一层函数确定第一个数，for循环，里面加上一个判断语句，是为了保证不重复，然后将它赋值为用过，再进行下一层循环，最后再回溯一次，第二三层循环也是同理。
当然还要加上终止条件，用过的数的数量等于要排的数量的时候，输出他们。

首先，我们要有一些变量和数组，一个ans[25]、n和flag[25]，分别是用来记录已选数，要选的数的数量和用没用过这个数，当然还要一个参数done表示用过的数的数量。

接下来for循环，if语句，赋值调用再回溯，代码：

for(int i = 1; i <= n; i++){
	if(flag[i] == 0){
		flag[i] = 1;
		ans[done]=i;
		rank(done+1);
		flag[i] = 0;
	}
}

最后再将终止条件加上，此时，我们可以直接输出。

if(done==n){
	for(int i = 0; i < n; i++){
		cout << setw(5) << ans[i]; 
	}
	cout << endl;
	return;
}

函数代码：

int ans[25]={0},n;
int flag[25] = {1};
void rank(int done){//全排列 
	if(done==n){
		
		for(int i = 0; i < n; i++){
			cout << setw(5) << ans[i]; 
		}
		cout << endl;
		return;
	}
	for(int i = 1; i <= n; i++){
		if(flag[i] == 0){
			flag[i] = 1;
			ans[done]=i;
			rank(done+1);
			flag[i] = 0;
		}
	}
}

再把主函数完成：

int main(int argc, char** argv) {
	cin >> n;
	rank(0);
	return 0;
}

完整代码

请勿抄袭

#include<bits/stdc++.h>//万能头文件 
using namespace std;
int ans[25]={0},n;
int flag[25] = {1};
void rank(int done){//全排列 
	if(done==n){
		
		for(int i = 0; i < n; i++){
			cout << setw(5) << ans[i]; 
		}
		cout << endl;
		return;
	}
	for(int i = 1; i <= n; i++){
		if(flag[i] == 0){
			flag[i] = 1;
			ans[done]=i;
			rank(done+1);
			flag[i] = 0;
		}
	}
} 
int main(int argc, char** argv) {
	cin >> n;
	rank(0);
	return 0;
}

#题解 全排列问题