STL中有兩個(gè)關(guān)于全排列的函數(shù)

• 求下一個(gè)全排列next_permutation(arr,arr+size);
• 求上一個(gè)全排列prev_permutation(arr,arr+size);
• 如果沒有下一個(gè)返回false

注意：

• 兩個(gè)函數(shù)都是從當(dāng)前狀態(tài)出發(fā)，尋找下一個(gè)全排列
• 返回為bool值

練習(xí)

• 給一個(gè)n，求第m個(gè)全排列
  題目鏈接
• 方法一：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++;//計(jì)數(shù)}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 當(dāng)前數(shù)組下標(biāo)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; }

總結(jié)

以上是生活随笔為你收集整理的HDU - 1027 全排列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。