康託展開

康託展開可以用來求一個 \(1\sim n\) 的任意排列的排名。

什麼是排列的排名？

把 \(1\sim n\) 的所有排列按字典序排序，這個排列的位次就是它的排名。

時間複雜度？

康託展開可以在 \(O(n^2)\) 的複雜度內求出一個排列的排名，在用到樹狀數組優化時可以做到 \(O(n\log n)\)。

怎麼實現？

因為排列是按字典序排名的，因此越靠前的數字優先級越高。也就是説如果兩個排列的某一位之前的數字都相同，那麼如果這一位如果不相同，就按這一位排序。

比如 \(4\) 的排列，\([2,3,1,4]<[2,3,4,1]\)，因為在第 \(3\) 位出現不同，則 \([2,3,1,4]\) 的排名在 \([2,3,4,1]\) 前面。

舉個栗子

我們知道長為 \(5\) 的排列 \([2,5,3,4,1]\) 大於以 \(1\) 為第一位的任何排列，以 \(1\) 為第一位的 \(5\) 的排列有 \(4!\) 種。這是非常好理解的。但是我們對第二位的 \(5\) 而言，它大於 第一位與這個排列相同的，而這一位比 \(5\) 小的 所有排列。不過我們要注意的是，這一位不僅要比 \(5\) 小，還要滿足沒有在當前排列的前面出現過，不然統計就重複了。因此這一位為 \(1,3\) 或 \(4\)，第一位為 \(2\) 的所有排列都比它要小，數量為 \(3\times 3!\)。

按照這樣統計下去，答案就是 \(1+4!+3\times 3!+2!+1=46\)。注意我們統計的是排名，因此最前面要 \(+1\)。

注意到我們每次要用到 當前有多少個小於它的數還沒有出現，這裏用樹狀數組統計比它小的數出現過的次數就可以了。

逆康託展開

因為排列的排名和排列是一一對應的，所以康託展開滿足雙射關係，是可逆的。可以通過類似上面的過程倒推回來。

如果我們知道一個排列的排名，就可以推出這個排列。因為 \(4!\) 是嚴格大於 \(3\times 3!+2\times 2!+1\times 1!\) 的，所以可以認為對於長度為 \(5\) 的排列，排名 \(x\) 除以 \(4!\) 向下取整就是有多少個數小於這個排列的第一位。

引用上面展開的例子

首先讓 \(46-1=45\)，\(45\) 代表着有多少個排列比這個排列小。\(\lfloor\frac {45}{4!}\rfloor=1\)，有一個數小於它，所以第一位是 \(2\)。

此時讓排名減去 \(1\times 4!\) 得到 \(21\)，\(\lfloor\frac {21}{3!}\rfloor=3\)，有 \(3\) 個數小於它，去掉已經存在的 \(2\)，這一位是 \(5\)。

\(21-3\times 3!=3\)，\(\lfloor\frac {3}{2!}\rfloor=1\)，有一個數小於它，那麼這一位就是 \(3\)。

讓 \(3-1\times 2!=1\)，有一個數小於它，這一位是剩下來的第二位，\(4\)，剩下一位就是 \(1\)。即 \([2,5,3,4,1]\)。

實際上我們得到了形如 有兩個數小於它 這一結論，就知道它是當前第 \(3\) 個沒有被選上的數，這裏也可以用線段樹維護，時間複雜度為 \(O(n\log n)\)。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用