欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}
相关标签: STL 全排列