概念

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

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

下文內(nèi)容都基于一個(gè)假設(shè)，即序列中不存在相同元素。對(duì)序列大小的比較做出定義：兩個(gè)長(zhǎng)度相同的序列，從兩者的第一個(gè)元素開始向后比較，直到出現(xiàn)一個(gè)不同元素（也可能就是第它們的第一個(gè)元素），該元素較大的序列為大，反之序列為?。蝗粢恢钡阶詈笠粋€(gè)元素都相同，那么兩個(gè)序列相等。

設(shè)當(dāng)前序列為pn，下一個(gè)較大的序列為pn+1，那么不存在pm，使得pn< pm< pn+1。

問題

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

數(shù)學(xué)推導(dǎo)

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

我們用來表示m個(gè)數(shù)的一種序列。設(shè)序列pn=<3 6 4 2>，根據(jù)定義可算得下一個(gè)序列pn+1=<4 2 3 6>。觀察pn可以發(fā)現(xiàn)，其子序列<6 4 2>已經(jīng)為減序，那么這個(gè)子序列不可能通過交換元素位置得出更大的序列了，因此必須移動(dòng)最高位3（即a1）的位置，且要在子序列<6 4 2>中找一個(gè)數(shù)來取代3的位置。子序列<6 4 2>中6和4都比3大，但6大于4。如果用6去替換3得到的序列一定會(huì)大于4替換3得到的序列，因此只能選4。將4和3的位置對(duì)調(diào)后形成排列<4 6 3 2>。對(duì)調(diào)后得到的子序列<6 3 2>仍保持減序，即這3個(gè)數(shù)能夠生成的最大的一種序列。而4是第1次作為首位的，需要右邊的子序列最小，因此4右邊的子序列應(yīng)為<2 3 6>，這樣就得到了正確的一個(gè)序列pn+1=<4 2 3 6>。

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

1) 若pn最右端的2個(gè)元素構(gòu)成一個(gè)增序子序列，那么直接反轉(zhuǎn)這2個(gè)元素使該子序列成為減序，即可得到pn+1。

2) 若pn最右端一共有連續(xù)的s個(gè)元素構(gòu)成一個(gè)減序子序列，令i = m - s，則有pn(i)< pn(i+1)，其中pn(i)表示排列pn的第i個(gè)元素。例如pn=<1 2 5 4 3>，那么pn的右端最多有3個(gè)元素構(gòu)成一個(gè)減序子集<5 4 3>，i=5-3=2，則有pn(i)=2 < 5=pn(i+1)。因此若將pn(i)和其右邊的子集s {pn(i+1), pn(i+2), ..., pn(m)}中任意一個(gè)元素調(diào)換必能得到一個(gè)較大的序列（不一定是下一個(gè)）。要保證是下一個(gè)較大的序列，必須保持pn(i)左邊的元素不動(dòng)，并在子集s {pn(i+1), pn(i+2), ..., pn(m)}中找出所有比pn(i)大的元素中最小的一個(gè)pn(j)，即不存在pn(k)∈ s且pn(i)< pn(k)< pn(j)，然后將二者調(diào)換位置?，F(xiàn)在只要使新子集{pn(i+1), pn(i+2), ..., pn(i), ...,pn(m)}成為最小序列即得到pn+1。注意到新子集仍保持減序，那么此時(shí)直接將其反轉(zhuǎn)即可得到pn+1{pn(1), pn(2), ..., pn(j), pn(m), pn(m-1), ..., pn(i), ..., pn(i+2), pn(i+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)。因?yàn)楦鞣N排列等可能出現(xiàn)，所以平均復(fù)雜度即為O(n)。

擴(kuò)展

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

設(shè)某個(gè)集合{a1, a2, ..., am}（a1

推廣可知，在確定前i（i

根據(jù)以上分析，對(duì)于給定的n（必有n<=m!）可以從第1位開始向右逐位地確定每一位元素。在第1位不變的前題下，后面m-1位一共可以生成(m-1)!中連續(xù)大小的序列。若n>(m-1)!，則第1位不會(huì)是a1，n中可以容納x個(gè)(m-1)!即代表第1位是ax。在確定第1位后，將第1位從原集合中刪除，得到新的集合{aq1, aq2, ..., aq3}（aq1

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

(1654 / 6!)取整得2，確定第1位為3，剩下的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)自程序控