823. 排列 (递归搜索树 · 排列)
原题链接 描述 给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式 共一行，包含一个整数 n。
输出格式 按字典序输出所有排列方案，每个方案占一行。
数据范围
代码语言：javascript复制1≤n≤9输入样例：
代码语言：javascript复制3输出样例：
代码语言：javascript复制1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1分析：
- 按照字典序排列分析
- 定义三个参数
int u用于记录当前排列的位数，int num[10]用于存放排列，bool st[10]={0}用于判断当前位置的数是否已经使用。
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int n,num[10];
bool st[10]={0};
void ff(int u,int num[],bool st[]){
if(u>n){ //如果u>n说明已经排列完成，循环输出排列
for(int i=1;i<=n;i ){
cout<<num[i]<<" ";
}
cout<<endl;
}
else{
for(int i=1;i<=n;i ){ //遍历循环判断结点
if(!st[i]){ //如果该位置的数未被使用
st[i]=1; //该位置的数标记为使用
num[u]=i; //记录该位置的数
ff(u 1,num,st); //进行入下一个位置递归
st[i]=0; //将该位置回溯为未使用状态(恢复现场)
}
}
}
}
int main(){
cin>>n;
ff(1,num,st);
return 0;
}扩展：
- 利用
STL中的next_permutation函数
next_permutation按照字典序生成下一个排列组合 复杂度O(n)排列范围[first,last)
代码：
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int main(){
int n,a[1000]; //a[]用于存放排列
cin>>n;
for(int i=1;i<=n;i ){
a[i]=i; //初始化排列
}
do{
for(int i=1;i<=n;i ){ //循环输出排列
cout<<a[i]<<" ";
}
cout<<endl;
}while(next_permutation(a 1,a n 1)); //如果下一个排列存在，则生成排列并执行
return 0;
}
