康托展開是一個全排列到一個自然數的雙射，常用于構建哈希表時的空間壓縮。 康托展開的實質是計算當前排列在所有由小到大全排列中的順序，因此是可逆的。

以下稱第x個全排列是都是指由小到大的順序。

康托展開求的是比該全排列小的數有多少個。

例如，3 5 7 4 1 2 9 6 8 展開為 98884。因為X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.

解釋：

排列的第一位是3，比3小的數有兩個，以這樣的數開始的排列有8!個，因此第一項為2*8!

排列的第二位是5，比5小的數有1、2、3、4，由于3已經出現，因此共有3個比5小的數，這樣的排列有7!個，因此第二項為3*7!

以此類推，直至0*0!

#define LL long long LL Ktuo(string a) {LL ans=0,count=0;LL factory[12] = { 1, 1, 2, 6, 24, 120,720, 5040, 40320, 362880, 3628800,39916800 };for(int i=0;i<a.length();++i){count=0;for(int j=i+1;j<a.length();++j){if(a[i]>a[j])++count;}ans+=count*factory[a.length()-1-i];}return ans;//比a小的排列有多少個 }

?

轉載于:https://www.cnblogs.com/A-way/archive/2013/04/28/3049781.html

總結

以上是生活随笔為你收集整理的康托展开模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。