本文最后更新于 963 天前,其中的信息可能已经有所发展或是发生改变。
原题链接
描述
给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
输入格式
共一行,包含一个整数 n。
输出格式
按字典序输出所有排列方案,每个方案占一行。
数据范围
输入样例:
输出样例:
| 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}
用于判断当前位置的数是否已经使用。
代码
| #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){ |
| 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)
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| int main(){ |
| int n,a[1000]; |
| 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; |
| } |