stl提供了權(quán)排列算法，以后暴力舉例就方便多啦

文末有手動(dòng)求，按字典序排序的全排列的第n個(gè)排列，的求法

?

next_permutation(a,a+4);? 檢測(cè)數(shù)組的a[0]到a[3]，如果不是“完全倒序”（如：4，3，2，1），就繼續(xù)執(zhí)行全排列

prev_permulation(a,a+4);? 與上面那個(gè)正相反

?

代碼舉例，next_permutation(a,a+4)：

#include<iostream> #include<algorithm> using namespace std; bool cmp(const int &a,const int &b){return a>b; } int main() { int ans[4]={1,2,3,4}; sort(ans,ans+4); /* 這個(gè)sort可以不用，因?yàn)閧1，2，3，4}已經(jīng)排好序*/ /*注意這步，如果是while循環(huán)，則需要提前輸出*/ for(int i=0;i<4;++i) cout<<ans[i]<<" "; cout<<endl; while(next_permutation(ans,ans+4)) { for(int i=0;i<4;++i) cout<<ans[i]<<" "; cout<<endl; }; return 0; }

?

prev_permulation(a,a+4)：

#include<iostream> #include<algorithm> using namespace std; bool cmp(const int &a,const int &b){return a>b; } int main() { int ans[4]={1,2,3,4}; sort(ans,ans+4,cmp); /* 這個(gè)sort可以不用，因?yàn)閧1，2，3，4}已經(jīng)排好序*/ /*注意這步，如果是while循環(huán)，則需要提前輸出*/ for(int i=0;i<4;++i) cout<<ans[i]<<" "; cout<<endl; while(prev_permutation(ans,ans+4)) { for(int i=0;i<4;++i) cout<<ans[i]<<" "; cout<<endl; }; return 0; }

以下內(nèi)容轉(zhuǎn)自：小與米

1.能否直接算出集合{1, 2, ..., m}的第n個(gè)排列？

舉例說明：如7個(gè)數(shù)的集合為{1, 2, 3, 4, 5, 6, 7}，要求出第n=1654個(gè)排列。

(1654 / 6!)取整得2，確定第1位為3（從0開始計(jì)數(shù)），剩下的6個(gè)數(shù){1, 2, 4, 5, 6, 7}，求第1654 % 6!=214個(gè)序列；

(214 / 5!)取整得1，確定第2位為2，剩下5個(gè)數(shù){1, 4, 5, 6, 7}，求第214 % 5!=94個(gè)序列；

(94 / 4!)取整得3，確定第3位為6，剩下4個(gè)數(shù){1, 4, 5, 7}，求第94 % 4!=22個(gè)序列；

(22 / 3!)取整得3，確定第4位為7，剩下3個(gè)數(shù){1, 4, 5}，求第22 % 3!=4個(gè)序列；

(4 / 2!)得2，確定第5為5，剩下2個(gè)數(shù){1, 4}；由于4 % 2!=0，故第6位和第7位為增序<1 4>；

因此所有排列為：3267514。

?

2. 給定一種排列，如何算出這是第幾個(gè)排列呢？

和前一個(gè)問題的推導(dǎo)過程相反。例如3267514：

后6位的全排列為6!，3為{1, 2, 3 ,4 , 5, 6, 7}中第2個(gè)元素（從0開始計(jì)數(shù)），故2*720=1440；

后5位的全排列為5!，2為{1, 2, 4, 5, 6, 7}中第1個(gè)元素，故1*5!=120；

后4位的全排列為4!，6為{1, 4, 5, 6, 7}中第3個(gè)元素，故3*4!=72；

后3位的全排列為3!，7為{1, 4, 5, 7}中第3個(gè)元素，故3*3!=18；

后2位的全排列為2!，5為{1, 4, 5}中第2個(gè)元素，故2*2!=4；

最后2位為增序，因此計(jì)數(shù)0，求和得：1440+120+72+18+4=1654

?

轉(zhuǎn)載于:https://www.cnblogs.com/ucandoit/p/8550915.html

總結(jié)

以上是生活随笔為你收集整理的next_permutation 与 prev_permutation(全排列算法)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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