概念

　　C++/STL中定義的next_permutation和prev_permutation函數(shù)則是非常靈活且高效的一種方法，它被廣泛的應(yīng)用于為指定序列生成不同的排列。本文將詳細(xì)的介紹prev_permutation函數(shù)的內(nèi)部算法。

　　按照STL文檔的描述，next_permutation函數(shù)將按字母表順序生成給定序列的下一個(gè)較大的排列，直到整個(gè)序列為降序?yàn)橹埂?prev_permutation函數(shù)與之相反，是生成給定序列的上一個(gè)較小的排列。二者原理相同，僅遍例順序相反，這里僅以 next_permutation為例介紹算法。

　　先對序列大小的比較做出定義：兩個(gè)長度相同的序列，從兩者的第一個(gè)元素開始向后尋找，直到出現(xiàn)一個(gè)不同元素(也可能就是第它們的第一個(gè)元素)，該元素較大的序列為大，反之序列為小;若一直到最后一個(gè)元素都相同，那么兩個(gè)序列相等。

　　設(shè)當(dāng)前序列為pn，下一個(gè)較大的序列為pn+1，這里蘊(yùn)藏的含義是再也找不到另外的序列pm，使得pn < pm < pn+1。

　　問題

　　給定任意非空序列，生成下一個(gè)較大或較小的排列。

　　過程

　　根據(jù)上述概念易知，對于一個(gè)任意序列，最小的排列是增序，最大的為減序。那么給定一個(gè)pn要如何才能生成pn+1呢?先來看下面的例子：

　　設(shè)3 6 4 2為pn，下一個(gè)序列pn+1應(yīng)該是4 2 3 6。觀察第一個(gè)序列可以發(fā)現(xiàn)pn中的6 4 2已經(jīng)為減序，在這個(gè)子集中再也無法排出更大的序列了，因此必須移動(dòng)3的位置且要找一個(gè)數(shù)來取代3的位置。在6 4 2中6和4都比3大，但6比3大的太多了，只能選4。將4和3的位置對調(diào)后形成排列4 6 3 2。注意，由于4和3大小的相鄰關(guān)系，對調(diào)后產(chǎn)生的子集6 3 2仍保持逆序，即該子集最大的一種排列。而4是第一次移動(dòng)到頭一位的，需要后面的子集為最小的排列，因此直接將6 3 2倒轉(zhuǎn)為2 3 6便得到了正確的一個(gè)序列pn+1。

　　下面歸納分析該過程。假設(shè)一個(gè)有m個(gè)元素的序列pn，其下一組較大排列為pn+1：

　　若pn的最后的2個(gè)元素構(gòu)成一個(gè)最小的增序子集，那么直接反轉(zhuǎn)這2個(gè)元素使該子集成為減序即可得到pn+1。理由是pn和pn+1的前面m-2 個(gè)元素都相等(沒有對前面的元素進(jìn)行操作)，僅能靠最后2個(gè)元素來分出大小。而這2個(gè)元素只能出現(xiàn)2種排列，其中較大的一種是減序。

　　若pn的最后最多有s個(gè)元素構(gòu)成一個(gè)減序子集，令i = m - s，則有pn(i) < pn(i+1)，因此若將pn(i)和pn(i+1)調(diào)換必能得到一個(gè)較大的排列(不一定是下一個(gè))，因此必須保持pn(i)之前的元素不動(dòng)，并在子集 {pn(i+1), pn(i+2), ..., pn(m)}中找到一個(gè)僅比pn(i)大的元素pn(j)，將二者調(diào)換位置。此時(shí)只要得到新子集{pn(i+1), pn(i+2), ..., pn(i), ...,pn(m)}的最小排列即可。注意到新子集仍保持減序，那么直接將其反轉(zhuǎn)即可得到最小的增序子集。

　　按以上步驟便可從pn得到pn+1了。

　　復(fù)雜度

　　最好的情況為pn的最后的2個(gè)元素構(gòu)成一個(gè)最小的增序子集，交換次數(shù)為1，復(fù)雜度為O(1)，最差的情況為1個(gè)元素最小，而后面的所有元素構(gòu)成減序子集，這樣需要先將第1個(gè)元素?fù)Q到最后，然后反轉(zhuǎn)后面的所有元素。交換次數(shù)為1+(n-1)/2，復(fù)雜度為O(n)。這樣平均復(fù)雜度即為O(n/2)。

　　C++/STL實(shí)現(xiàn)

　　01#include

　　02#include

　　03#include

　　04using namespace std;

　　05//主函數(shù)，算法詳見相關(guān)說明

　　06int main(void) {

　　07 //循環(huán)處理輸入的每一個(gè)字符串

　　08 for (string str; cin >> str;) {

　　09 if (str.empty()) {

　　10 continue;

　　11 }

　　12 //如果字符串只有1個(gè)字符，則直接輸出結(jié)束

　　13 if (str.length() <= 1) {

　　14 cout << "No more Permutation" << endl;

　　15 }

　　16 //iPivot為右邊最大減序子集左邊相鄰的一個(gè)元素

　　17 string::iterator iPivot = str.end(), iNewHead;

　　18 //查找右邊最大的減序子集

　　19 for (--iPivot; iPivot != str.begin(); --iPivot) {

　　20 if (*(iPivot - 1) < *iPivot ) {

　　21 break;

　　22 }

　　23 }

　　24 //如果整個(gè)序列都為減序，則重排結(jié)束。

　　25 if (iPivot == str.begin()) {

　　26 cout << "No more Permutation" << endl;

　　27 }

　　28 //iPivot指向子集左邊相鄰的一個(gè)元素

　　29 iPivot--;

　　30 //iNewHead為僅比iPivot大的元素，在右側(cè)減序子集中尋找

　　31 for (iNewHead = iPivot + 1; iNewHead != str.end(); ++iNewHead) {

　　32 if (*iNewHead < *iPivot) {

　　33 break;

　　34 }

　　35 }

　　36 //交換iPivot和iNewHead的值，但不改變它們的指向

　　37 iter_swap(iPivot, --iNewHead);

　　38 //反轉(zhuǎn)右側(cè)減序子集，使之成為最小的增序子集

　　39 reverse(iPivot + 1, str.end());

　　40 //本輪重排完成，輸出結(jié)果

　　41 cout << str << endl;

　　42 }

　　43 return 0;

　　44}