HDU - 1027 全排列
程序员文章站
2022-03-01 23:20:57
...
STL中有两个关于全排列的函数
- 求下一个全排列next_permutation(arr,arr+size);
- 求上一个全排列prev_permutation(arr,arr+size);
- 如果没有下一个返回false
注意:
- 两个函数都是从当前状态出发,寻找下一个全排列
- 返回为bool值
练习
- 给一个n,求第m个全排列
题目链接 - 方法一:STL
#include<iostream>
#include<algorithm>
#define N 1005
using namespace std;
int inf=0x3f3f3f3f;
int a[N];
int main(){
int n,m;
while(cin>>n>>m){
for(int i=1;i<=n;i++){
a[i]=i;
}
int sum=1;
while(sum!=m){
next_permutation(a+1,a+n+1);//起始位置,起始+size
sum++;//计数
}
cout<<a[1];
for(int i=2;i<=n;i++)
cout<<" "<<a[i];
cout<<endl;
}
return 0;
}
- 方法二:dfs模拟(m较小的情况)
#include<iostream>
#include<algorithm>
#include<string.h>
#define N 200005
using namespace std;
int inf=0x3f3f3f3f;
int n,m,sum;
int a[N];
int vis[N]={0};
void dfs(int now){//now 当前数组下标
if(sum==m)
return ;
if(now>n){
if(++sum==m){
cout<<a[1];
for(int i=2;i<=n;i++)
cout<<" "<<a[i];
cout<<endl;
return ;
}
return ;//这里忘记写return,TLE好几次!
}
for(int i=1;i<=n;i++){
if(vis[i]==0){
vis[i]=1;
a[now]=i;
dfs(now+1);
if(sum==m)//剪枝
return ;
vis[i]=0;//回溯
}
}
return;
}
int main(){
while(cin>>n>>m){
memset(vis,0,sizeof(vis));//每次清零
sum=0;
dfs(1);
}
return 0;
}