[//]: # 用枚举每个数字应该放到哪个位置为什么不行呢
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=20;
//字典序:strcmp 按每位比较
//全排列是n!个方案
//顺序: 1、枚举每个位置放哪个数 2、枚举每个数放哪个位置
bool state[N];//表状态
int arr[N];//存方案
//这里的是第一种枚举的顺序
//这里的u表示的是枚举到了第几次位置
void dfs(int u){
if(u>n){//如果枚举的位置超出了n的范围,就说明我们已经枚举完了,输出结果
for(int i=1;i<=n;i++) printf("%d ",arr[i]);
cout<<endl;
return ;
}
for(int i=1;i<=n;i++){//i是枚举的数字,
if(!state[i]){//如果这个数字没有被选
state[i]=true;//就选择它
arr[u]=i;//把他记录下来
dfs(u+1);//继续选择下一个数
//恢复现场
state[i]=false;//如果不选择这个数
arr[u]=0;//就把原来的赋值变回0
}
}
}
//接下来看第二种枚举的顺序:枚举每个数放哪个位置
//思路:每次枚举数要放在第几个位置,如果位置都枚举完就输出答案、
//这中间需要枚举每个数放的位置:
//判断这个位置有没有被放进数字,如果没有被放进数组就放进数字,然后继续枚举下一个。
/*
void dfs(int u){//枚举每个数
//出口:如果枚举数的大小超过最大值n就输出方案并退出
if(u>n){
for(int i=1;i<=n;i++) printf("%d ",arr[i]);
printf("\n");
return ;
}
for(int i=1;i<=n;i++){
//枚举每个位置
if(!state[i]){//如果这个位置是没有被放进数字的
//选择这个位置放进数字
state[i]=true;//就放进去数字
arr[i]=u;//那这个位置的数字就是u
dfs(u+1);//继续枚举下一个数
//不选择这个位置放进数字
state[i]=false;
arr[i]=0;
}
}
}
*/
/*
如果使用第二种顺序 枚举每个数放哪个位置是不能得到字典序排序的
1 2 3
1 3 2
2 1 3
3 1 2
2 3 1
3 2 1
*/
int main(){
cin>>n;
dfs(1);
return 0;
}