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