當(dāng)年在考場(chǎng)上第一次看到“火星人”這道題心里又驚又喜。驚的是題面很有意思外星人用手指數(shù)數(shù)每個(gè)手指還都有自己的編號(hào)喜的是它本質(zhì)上就是全排列字典序的下一個(gè)排列這不就是當(dāng)年教科書上“求后繼排列”的經(jīng)典問題嗎結(jié)果真動(dòng)手寫的時(shí)候我卡了挺久。因?yàn)镹和M都可以到10000直接傻乎乎地從第一個(gè)排列開始枚舉到目標(biāo)位置根本不可能而如果只會(huì)用DFS全排列去“數(shù)”N一大早就爆了。這篇文章就從洛谷P1088這道題出發(fā)把“給定一個(gè)排列求它后面第M個(gè)字典序排列”這件事徹底講清楚。既有考場(chǎng)上一行STL帶走的偷懶做法也有原理層面的排列序號(hào)進(jìn)位法。不管你是備戰(zhàn)NOIP、CSP-J/S的選手還是剛學(xué)全排列、康托展開的初學(xué)者都能找到自己能用的東西。1. 題目解讀與核心難點(diǎn)1.1 火星人的手指密碼到底是什么先還原一下題面火星人有一排N根手指每根手指都有一個(gè)不重復(fù)的編號(hào)從1到N。他們計(jì)數(shù)的方式很特別把手指從左到右排成一列用一個(gè)排列來表示一個(gè)數(shù)。所有的排列按照字典序從小到大排列好比如N3的時(shí)候就是123、132、213、231、312、321這樣一路排下去。外星人會(huì)先伸出某個(gè)排列然后告訴你“我要繼續(xù)往后數(shù)M個(gè)數(shù)”你要算出他最后擺出來的那個(gè)排列是什么。輸入給的是N、M以及當(dāng)前伸出的那個(gè)排列。N和M的范圍都是10000以內(nèi)。也就是說N10000、M10000是可能出現(xiàn)的而且題目只給一個(gè)測(cè)試點(diǎn)時(shí)限一般是1秒左右。這不是一道讓你去腦補(bǔ)“外星人有多神奇”的題它考的就是排列生成、字典序以及如何處理大規(guī)模數(shù)據(jù)。1.2 為什么不能直接從第一個(gè)排列開始數(shù)很多新手第一反應(yīng)是既然所有排列已經(jīng)按字典序排好了那我用搜索把從123...N開始的排列一個(gè)一個(gè)生成出來數(shù)到目標(biāo)位置不就行了這個(gè)思路在N很小的時(shí)候完全成立。N3、N4的時(shí)候DFS把全排列枚舉出來再從頭找目標(biāo)排列的下M個(gè)完全沒問題。但問題是N最大到10000。全排列的個(gè)數(shù)是N!這個(gè)數(shù)字增長得極其恐怖N10就已經(jīng)300多萬個(gè)N10000根本不可能一一枚舉。所以這道題考查的重點(diǎn)不是“生成全排列再查找”而是“已知一個(gè)排列如何在這個(gè)有序的排列序列中向后跳躍M步”。換個(gè)更簡(jiǎn)單的說法123和132是兩個(gè)相鄰的排列但要你直接從“87654321”這種排列往后跳10000步總不能把它前面幾十億個(gè)排列全掃一遍吧我們需要的是排列與排列之間的“加減法”運(yùn)算而不是把所有排列都暴力列出來。1.3 數(shù)據(jù)范圍直接決定思路走向看到N、M都是10000其實(shí)是在暗示你可以接受O(NM)級(jí)別的解法也可以接受O(N log N)級(jí)別的解法但絕對(duì)不能接受O(N!)或者O(2^N)之類的東西。換句話說這道題給了兩條路一條路是利用STL的next_permutation函數(shù)每次在當(dāng)前排列上向后走一步重復(fù)M次。由于next_permutation的單次平均代價(jià)很低實(shí)際運(yùn)行往往跑不滿O(NM)很多選手用這個(gè)寫法直接AC。另一條路是把排列看成一個(gè)奇特的“數(shù)字”通過進(jìn)制進(jìn)位的思想直接從原排列加上M得到新排列。這個(gè)寫起來復(fù)雜一點(diǎn)但時(shí)間復(fù)雜度是穩(wěn)定的O(N log N)。我當(dāng)年在考場(chǎng)上先用了第一種方法AC之后又回頭研究第二種發(fā)現(xiàn)它對(duì)于理解康托展開、逆康托展開非常有幫助。下面兩章分別展開講。2. 思路ASTL next_permutation 通關(guān)最簡(jiǎn)單寫法2.1 next_permutation 到底做了什么C的STL里有一個(gè)函數(shù)叫next_permutation它做的事情就是對(duì)于一個(gè)數(shù)組表示的排列原地修改它使它變成字典序中的下一個(gè)排列。如果當(dāng)前排列已經(jīng)是字典序中最大的那個(gè)比如N3時(shí)的321函數(shù)會(huì)返回false并把數(shù)組改成最小的排列123。它的原理其實(shí)只有三步從后往前找到第一個(gè)滿足a[i] a[i1]的位置i這個(gè)位置就是需要變動(dòng)的“關(guān)鍵位置”。如果整個(gè)數(shù)組從后往前一直是降序說明已經(jīng)不存在更大的排列。再從后往前找到第一個(gè)比a[i]大的元素a[j]。交換a[i]和a[j]然后把i1到末尾這一段反轉(zhuǎn)。因?yàn)檫@段原本是降序反轉(zhuǎn)后變成升序剛好得到字典序中緊挨著的下一個(gè)排列。舉個(gè)例子123的下一個(gè)排列是132。從后往前看2 3所以i指向2這個(gè)位置然后從后往前找第一個(gè)比2大的數(shù)找到3交換得到132然后i1到末尾只有一位不用反轉(zhuǎn)完成。整個(gè)next_permutation的時(shí)間復(fù)雜度最壞是O(N)但平均情況下只需要掃描尾部一小段。比如從123456到123465只需要改動(dòng)最后兩位。這也是為什么很多人說“M次調(diào)用也能過”的根本原因。2.2 考場(chǎng)上一行STL帶走的代碼對(duì)于P1088代碼短到令人感動(dòng)#include bits/stdc.h using namespace std; int n, m; int a[10005]; int main() { scanf(%d%d, n, m); for (int i 1; i n; i) { scanf(%d, a[i]); } while (m--) { next_permutation(a 1, a n 1); } for (int i 1; i n; i) { printf(%d , a[i]); } printf(\n); return 0; }注意next_permutation接收的是迭代器區(qū)間左閉右開。數(shù)組從1開始存儲(chǔ)時(shí)就是a1到an1。如果誰把右邊界寫成an那永遠(yuǎn)只會(huì)對(duì)前n-1個(gè)元素做排列最后一個(gè)元素始終不變提交上去等著Wrong Answer吧。我在這里要提一句如果你使用的是vector對(duì)應(yīng)的寫法是next_permutation(v.begin(), v.end())不需要加1因?yàn)関ector迭代器是從0開始的。別在vector、數(shù)組混用的時(shí)候搞混。2.3 復(fù)雜度、風(fēng)險(xiǎn)與考場(chǎng)上怎么選這個(gè)寫法的時(shí)間復(fù)雜度理論上限是O(NM)也就是1e8。有不少人拿到OJ上一跑幾百毫秒就過了越覺得玄學(xué)。其實(shí)next_permutation每次調(diào)用都要從后往前找第一個(gè)上升點(diǎn)。如果排列尾部比較隨機(jī)大多數(shù)情況下上升點(diǎn)很快就能找到掃描長度很短。只有在排列呈整體降序、接近末尾的時(shí)候單次掃描才會(huì)接近O(N)。所以實(shí)際運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)好于最壞情況。不過OI比賽里“實(shí)際跑得快”和“理論上說得過去”是兩回事。我見過一些選手因?yàn)橐蕾嘢TL而翻車不是這道題翻車而是遇到某些數(shù)據(jù)恰好卡在next_permutation的壞情況下導(dǎo)致超時(shí)。所以我的建議是如果你現(xiàn)在打的是普及組、CSP-J這類比賽N、M在10000以內(nèi)用next_permutation完全可行不要有心理負(fù)擔(dān)。如果你想扎實(shí)掌握排列算法或者擔(dān)心以后遇到N、M更大的變種題那就一定要會(huì)下一章的手寫進(jìn)位法。STL雖好但背后的原理才是通用能力。3. 思路B排列序號(hào)進(jìn)位法原理更優(yōu)的解法3.1 排列也可以當(dāng)成一個(gè)“數(shù)字”來算如果說next_permutation是“一步一步走”那進(jìn)位法就是“坐電梯直達(dá)目標(biāo)層”。要理解它先得明白一個(gè)很漂亮的性質(zhì)任何一個(gè)排列都能唯一轉(zhuǎn)換成一個(gè)“變進(jìn)制數(shù)”。這個(gè)變進(jìn)制數(shù)每一位表示的含義是當(dāng)前這個(gè)位置上右邊剩下沒有用過的數(shù)字中有多少個(gè)比它小。舉個(gè)N3的例子看排列231第一位是2。在還沒用過的數(shù)字{1,2,3}中比2小的只有1所以這一位對(duì)應(yīng)的系數(shù)是1。第二位是3。此時(shí)還剩下{1,3}比3小的只有1所以這一位系數(shù)也是1。第三位是1。此時(shí)剩{1}比1小的一個(gè)都沒有系數(shù)為0。所以231對(duì)應(yīng)的系數(shù)序列是(1,1,0)。這個(gè)系數(shù)序列從左到右乘以(n-1)!、(n-2)!、...、0!再累加起來就是這個(gè)排列在字典序中的編號(hào)。計(jì)算一下1×2! 1×1! 0×0! 3。也就是說在字典序從0開始編號(hào)的情況下231確實(shí)是第3個(gè)排列。你可以對(duì)照一下0號(hào)是1231號(hào)是1322號(hào)是2133號(hào)正好是231完全吻合。這就是經(jīng)典的康托展開。很多教材上是直接給公式初學(xué)者看得一臉懵。我自己當(dāng)年學(xué)的時(shí)候是把它想象成“按位確定排列”的編號(hào)第一位有N種選擇其中第x小的數(shù)字就對(duì)應(yīng)x×(N-1)!第二位有N-1種選擇又對(duì)應(yīng)y×(N-2)!……一路乘下去剛好把一個(gè)排列映射成一個(gè)整數(shù)。3.2 在變進(jìn)制上直接加M坐電梯到目標(biāo)既然排列能映射成序號(hào)那從當(dāng)前排列向后數(shù)M個(gè)本質(zhì)上就是“當(dāng)前排列序號(hào) M”對(duì)應(yīng)的那個(gè)排列。如果N不太大比如幾百以內(nèi)直接用康托展開算出序號(hào)加上M再做逆康托展開還原就能得到答案。但N到10000時(shí)(N-1)!這個(gè)數(shù)字早就超出long long的范圍不能硬算階乘。聰明一點(diǎn)的做法是不要真的去算那個(gè)巨大的序號(hào)而是模擬“在這個(gè)變進(jìn)制數(shù)上加上M”的過程。這跟十進(jìn)制加法一樣從低位開始一位一位地加超出某一位的進(jìn)制范圍就向高位進(jìn)位。區(qū)別只在于每一位的進(jìn)制不一樣所以叫變進(jìn)制。我把具體算法寫出來。首先求系數(shù)數(shù)組c[i]其中c[i]表示a[i]右邊有多少個(gè)數(shù)字比a[i]小。接下來令cur M從數(shù)組最后一個(gè)位置往前處理把當(dāng)前位的系數(shù)c[i]加上cur。這一位能取的最大范圍是“右邊剩余數(shù)字個(gè)數(shù)”更準(zhǔn)確地說從右往左數(shù)第q個(gè)位置對(duì)應(yīng)的取值個(gè)數(shù)是q第0個(gè)位置固定為0即最后一個(gè)位置只能取0。于是令c[i] c[i] % qcur c[i] / q其中q從2開始遞增也就是右邊的位置依次對(duì)應(yīng)q2、3、4...。循環(huán)結(jié)束后新的c數(shù)組就是目標(biāo)排列對(duì)應(yīng)的系數(shù)。是不是有點(diǎn)繞我拿231這個(gè)排列M1來驗(yàn)證。231的系數(shù)是(1,1,0)。從右往左最右邊一位系數(shù)0加上cur1得到1。這一位固定沒有余地模1得0進(jìn)位1。中間一位系數(shù)1加上進(jìn)位1得到2。這一位的范圍是{0,1}也就是能選2種模2得0進(jìn)位1。最左邊一位系數(shù)1加上進(jìn)位1得到2。這一位范圍是{0,1,2}能選3種模3得2進(jìn)位0。于是新的系數(shù)是(2,0,0)。根據(jù)3.1的公式2×2! 0×1! 0×0! 4正好是312的編號(hào)。因?yàn)?31的編號(hào)是3加1等于4所以目標(biāo)排列就是312。整個(gè)計(jì)算過程與數(shù)字的加法進(jìn)位完全一致只是進(jìn)制不同而已。寫代碼的時(shí)候可以用一個(gè)整數(shù)數(shù)組直接在原系數(shù)上做進(jìn)位不需要真算階乘非常清爽。3.3 用樹狀數(shù)組還原目標(biāo)排列進(jìn)位完成后得到的是系數(shù)數(shù)組還需要還原成排列。還原過程其實(shí)很簡(jiǎn)單從左到右根據(jù)每一位的系數(shù)在當(dāng)前還沒使用的數(shù)字集合中選取第系數(shù)1小的數(shù)字。因?yàn)橄禂?shù)為x表示“在剩余數(shù)字中有x個(gè)數(shù)字比它小”所以它就是剩余數(shù)字中第x1小的那個(gè)。這里最直接的辦法是開一個(gè)bool數(shù)組標(biāo)記某個(gè)數(shù)字是否用過然后每次從1開始掃描到N找第x1個(gè)未使用的數(shù)字。但這樣是O(N)找一個(gè)數(shù)字總復(fù)雜度O(N^2)N10000時(shí)就是1e8運(yùn)氣不好會(huì)超時(shí)。用樹狀數(shù)組維護(hù)“某個(gè)編號(hào)是否被使用”可以在O(log N)時(shí)間內(nèi)完成“找第k個(gè)可用的數(shù)字”這件事。思路是用樹狀數(shù)組存儲(chǔ)每個(gè)數(shù)字的剩余狀態(tài)1表示還沒被使用。給定系數(shù)c[i]要找的就是前綴和恰好等于c[i]1的最左位置這個(gè)可以用二分答案配合樹狀數(shù)組查詢實(shí)現(xiàn)也可以直接在樹狀數(shù)組上做“樹上二分”也就是在bit上找第k個(gè)1的位置。#include bits/stdc.h using namespace std; const int MAXN 10005; int n, m; int a[MAXN], c[MAXN]; int tree[MAXN]; int lowbit(int x) { return x -x; } void add(int idx, int val) { for (int i idx; i n; i lowbit(i)) { tree[i] val; } } int sum(int idx) { int res 0; for (int i idx; i 0; i - lowbit(i)) { res tree[i]; } return res; } // 在樹狀數(shù)組中找第k個(gè)1的位置 int kth(int k) { int pos 0; for (int i 20; i 0; --i) { int nxt pos (1 i); if (nxt n tree[nxt] k) { k - tree[nxt]; pos nxt; } } return pos 1; } int main() { scanf(%d%d, n, m); for (int i 1; i n; i) { scanf(%d, a[i]); } // 第一步計(jì)算每個(gè)位置右邊比自己小的數(shù)字個(gè)數(shù) // 用樹狀數(shù)組邊插入邊統(tǒng)計(jì)也可以直接暴力O(N^2) memset(tree, 0, sizeof(tree)); for (int i n; i 1; --i) { c[i] sum(a[i] - 1); add(a[i], 1); } // 第二步模擬進(jìn)位加上m int base 2; for (int i n; i 1; --i) { c[i] m; m c[i] / base; c[i] % base; base; } // 第三步根據(jù)系數(shù)還原排列 memset(tree, 0, sizeof(tree)); for (int i 1; i n; i) { add(i, 1); } for (int i 1; i n; i) { int pos kth(c[i] 1); printf(%d , pos); add(pos, -1); } printf(\n); return 0; }我來解釋幾個(gè)關(guān)鍵細(xì)節(jié)。第一步求c[i]的時(shí)候從右往左遍歷每次查詢當(dāng)前樹狀數(shù)組中小于a[i]的數(shù)字個(gè)數(shù)然后把a(bǔ)[i]本身插入。這樣就得到了“右邊比它小的數(shù)字個(gè)數(shù)”。第二步的進(jìn)位從右往左base從2開始遞增因?yàn)樽钣疫呉晃挥肋h(yuǎn)只能取0倒數(shù)第二位只能取0或1再往前一位可以取0、1、2以此類推。第三步初始化樹狀數(shù)組全部為1表示所有數(shù)字都未使用然后依次取出第c[i]1小的數(shù)字取出來后標(biāo)記為0。這個(gè)算法的總復(fù)雜度是O(N log N)N10000時(shí)非常快哪怕N開到1e6也能扛住。3.4 兩種寫法的硬碰硬對(duì)比對(duì)比維度STL next_permutation排列序號(hào)進(jìn)位法代碼長度很短十幾行較長需要樹狀數(shù)組時(shí)間復(fù)雜度理論最壞O(NM)實(shí)際遠(yuǎn)快O(N log N)穩(wěn)定原理難度低會(huì)用STL即可高需要理解康托展開與逆展開優(yōu)點(diǎn)不易寫錯(cuò)適合考場(chǎng)速戰(zhàn)效率穩(wěn)定可擴(kuò)展到N很大缺點(diǎn)依賴STL遇到數(shù)據(jù)卡可能超時(shí)容易在進(jìn)位、還原細(xì)節(jié)上出錯(cuò)從應(yīng)試角度講這兩種方法都是正解。從學(xué)習(xí)角度講我更推薦把進(jìn)位法徹底弄懂因?yàn)樗軒湍愦蛲低姓归_、逆康托展開、求第K小字典序排列等一系列問題。4. 常見問題與調(diào)試心得4.1 我明明照著文章寫的為什么Wrong Answer這道題最常見的“想讓代碼通過但怎么都差一點(diǎn)”的坑我整理成了一張速查表癥狀可能原因解決辦法結(jié)果總是比答案大一點(diǎn)多調(diào)用了一次next_permutation注意題目要求“后續(xù)第M個(gè)”不是“執(zhí)行M1次”結(jié)果完全亂掉數(shù)組下標(biāo)與迭代器區(qū)間傳錯(cuò)next_permutation(a1, an1)是左閉右開不要寫an進(jìn)位法結(jié)果部分正確進(jìn)位時(shí)base初始值寫錯(cuò)從右往左base從2開始遞增別從1開始進(jìn)位法輸出有重復(fù)或缺失還原系數(shù)時(shí)選了已使用的數(shù)字確認(rèn)kth函數(shù)找到的是第c[i]1個(gè)未使用數(shù)字找完立刻刪掉本地跑大樣例超時(shí)用了O(N^2)暴力找第k小改用樹狀數(shù)組二分或直接在BIT上跳輸出末尾多個(gè)空格每行輸出后等多數(shù)OJ接受行尾空格但比賽建議控制格式其中“base從1開始”這個(gè)錯(cuò)誤我記得特別清楚。為什么最后一位永遠(yuǎn)只能取0因?yàn)槟阋呀?jīng)確定到最后一個(gè)數(shù)字時(shí)剩下的數(shù)字只有一個(gè)它不可能是“比某個(gè)數(shù)字小”的第幾個(gè)所以系數(shù)固定為0。從右往左第2位開始才有0/1兩種選擇所以base從2開始。4.2 推薦的對(duì)拍與壓力測(cè)試技巧一道題寫完光靠樣例遠(yuǎn)遠(yuǎn)不夠。我習(xí)慣寫一個(gè)對(duì)拍器來驗(yàn)證。生成一個(gè)小N比如N8以內(nèi)的隨機(jī)排列用最暴力的辦法枚舉全排列數(shù)到目標(biāo)位置再用你的算法算一遍對(duì)比結(jié)果是否一致。如果小數(shù)據(jù)沒錯(cuò)再逐漸加大N測(cè)試性能。C寫暴力驗(yàn)證非常簡(jiǎn)單先生成目標(biāo)起始排列然后用next_permutation循環(huán)M次這個(gè)本身就可以當(dāng)作暴力標(biāo)準(zhǔn)答案。然后再把進(jìn)位法跑一邊兩個(gè)結(jié)果比對(duì)。如果N8、M100時(shí)結(jié)果都能對(duì)上基本可以判斷算法核心沒問題剩下的就是邊界條件。性能測(cè)試部分我建議專門構(gòu)造一個(gè)接近降序的排列比如N10000起始排列是987654321...這樣的順序M取10000。這種數(shù)據(jù)對(duì)STL方法的壓力最大如果跑下來沒超時(shí)說明這道題用STL確實(shí)是穩(wěn)的。4.3 從這道題延伸出去的算法清單這道題雖然只是普及組但它的內(nèi)核非常硬核。排列相關(guān)的幾類問題完全可以串成一條學(xué)習(xí)線康托展開求一個(gè)排列在字典序中的編號(hào)常用于狀態(tài)壓縮DP做哈希。逆康托展開根據(jù)編號(hào)恢復(fù)排列上面的進(jìn)位法本質(zhì)上就是這個(gè)。求第K個(gè)字典序排列標(biāo)答思路就是逆康托展開N大時(shí)用樹狀數(shù)組或線段樹優(yōu)化。可重集排列序列里允許重復(fù)元素時(shí)排列數(shù)的計(jì)算要用到多重集排列公式組合數(shù)選階乘。部分排列從N個(gè)數(shù)字中選K個(gè)排列的問題編號(hào)方式和全排列相似但每一位選項(xiàng)范圍更復(fù)雜。如果你把“火星人”完全吃透后面的這些算法會(huì)順暢很多。因?yàn)樽冞M(jìn)制進(jìn)位的核心思想就是“每一位的選項(xiàng)個(gè)數(shù)不同”而可重集、部分排列都是在這個(gè)思想上稍作修改。最后分享一個(gè)我的個(gè)人習(xí)慣我現(xiàn)在帶學(xué)生刷題總會(huì)在講完STL解法之后逼著他們親手寫一遍進(jìn)位法就算題目用STL能過也必須寫。原因很簡(jiǎn)單STL的next_permutation是別人做好的輪子你能用別人也能用但考場(chǎng)上萬一題目升級(jí)成“給定一個(gè)10萬位的大排列求后面第10萬個(gè)排列”STL那套很可能就被數(shù)據(jù)按在地上摩擦。進(jìn)位法雖然代碼多一些但它逼著你理解排列的本質(zhì)理解變進(jìn)制理解樹狀數(shù)組的妙用。理解過一遍之后以后再遇到類似題心態(tài)完全不一樣。還有一個(gè)小技巧當(dāng)年我被“系數(shù)還原”卡住的時(shí)候喜歡拿N3把所有排列手寫一遍然后對(duì)著紙演算進(jìn)位過程。紙上畫三分鐘比盯著屏幕干想半小時(shí)效率高得多。如果你今天在這道題上栽了跟頭別急著翻題解先把手上的N調(diào)成3或4把排列一張一張畫出來再對(duì)比算法每一步的結(jié)果很多疑點(diǎn)會(huì)瞬間解開。