HDU - 1027 全排列

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;
}