文章目录简单原理纸箱展开逆纸箱展开例：应用
简单地叙述
康托展开是完全排列在一个自然数上的双射，常用于构造hash表的空间压缩。 设定n的个数(1，2，3，4，…，n )，也可以有组成的不同(n！ 种)的排列组合，色调展开表示n个不同要素的所有排列中比当前排列组合小的个数，表示n个不同要素的所有排列中的当前排列组合的位次(当前位次=比当前排列组合小的个数1 )
原理X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!
其中a[i]是整数，并且0=a[i]=i，0=i n指示在当前未出现的元素中是第几个。 这就是展开情节。
例如，如果有3个个数(1，2，3 )，则其排列的组合和与其对应的铁路超高展开值如下。
组合顺序纸箱展开值12310 * 2！ 0 * 1！ 0 * 0！ 013220 * 2！ 1 * 1！ 0 * 0！ 121331 * 2！ 0 * 1！ 0 * 0！ 223141 * 2！ 1 * 1！ 0 * 0！ 331252 * 2！ 0 * 1！ 0 * 0！ 432162 * 2！ 1 * 1！ 0 * 0！ 5例如其中231 :
在计算之前的数组组合数(123、132、213 )时，小于开头，即小于2的所有数组“1 * 2！ ”，第1位为2，第2位小于3的所有排列“1 * 1！ )，前2位为23，第3位小于1的所有数组(0 * 0)！ 的和就可以了。 康托展开为1 * 2！ 1 * 1 0 * 0=3。 所以小于231的组合有三个，所以231的排名是4。 康托展开进一步举例说明。
(1，2，3，4，5 )在五个排列的组合中，计算34152的铁路超高展开值。
顶部是3，小于3的数是1和2这两个，a[5]=2，顶部小于3的所有排列组合都是a[5]*(5-1)！ 第二位是4，有两个小于4的数，1和2。 请注意，这里不能计算3。 因为3已经在第一位，所以实际上在第二位之后计算小于4的个数。 因此，由于a[4]=2的第3位是1，其次的小于1的数有0个，所以a[3]=0的第4位是5，其次的小于5的数有1个，为2，所以a[2]=1的最后的位可以不计算因为在那之后已经没有计数了，所以a[1]被固定为0。 公式：
X=2 * 4！ 2 * 3！ 0 * 2！ 1 * 1！ 0 * 0！=2 * 24 2 * 6 1=61
因此，小于34152的组合有61个，34152排在第62位。 具体的代码实现如下。 (假设数组数小于10个。 ) )
staticconstintfac [ ]={ 1，1，2，6，24，120，720，5040，40320，362880 }； //阶乘intcantor(int*a，int n ) intx=0； for(intI=0； i n； I({intsmaller=0； //在当前位之后加上比其小的个数for(intj=I1； j n； j () if ) a[j]a[I] ) smaller； }x =FAC[n - i - 1] * smaller； //铁路超高展开累积(}return x； //纸箱展开值(tips:这里主要为了说明纸箱展开的思路，实现的算法复杂度为o(n^2)，实际上在n较大的情况下，内层循环计算在当前位数之后比当前位数更低
逆色调展开如最初所述，色调展开是完全排列为1个自然数的线段树，因此是可逆的。 即，对于上述例子，如果对[ 1，2，3，4，5 ]赋予61，则可以计算出排列的组合为34152。 通过上述计算过程可以很容易地反算出来，具体过程如下。
在61/4！=2余13，a[5]=2，因为显示有两个小于顶部的数，所以顶部是3。 在13/3！=2馀1表示a[4]=2，由于第二位数之后有两个小于第二位数的数，所以第二位数表示4。 用1/2！=0馀1表示a[3]=0，表示第3位之后没有小于第3位的数，因此第3位是1。 以1/1！=1馀数0表示a[2]=1，表示第2位之后有一个小于第4位的数，因此第4位是5。 最后一个人当然是剩下的几2。 通过以上分析，求得序列组合为34152。 具体的代码实现如下。 (假设数组数小于10个。 ) )
staticconstintfac [ ]={ 1，1，2，6，24，120，720，5040，40320，362880 }； //阶乘//铁路超展开逆运算voiddecantor(intx，int n ) { vectorint rest； //存储当前选项数，保证有序的for (inti=1； i=n； I ) v.push_back(I )；
vector<int> ans; // 所求排列组合 for(int i=n;i>=1;i--) { int r = x % FAC[i-1]; int t = x / FAC[i-1]; x = r; a.push_back(v[t]); // 剩余数里第t+1个数为当前位 v.erase(v.begin()+t); // 移除选做当前位的数 }} 示例：leetcode题目 60. 第k个排列
直接套逆康托展开即可，需要处理的是求的是第k个排列，那么其对应的康托展开值应该减1 （k - 1）。
应用最多的场景也是上述讲的它的特性。
给定一个自然数集合组合一个全排列，所其中的一个排列组合在全排列中从小到大排第几位。
在上述例子中，在（1，2，3，4，5）的全排列中，34152的排列组合排在第62位。
反过来，就是逆康托展开，求在一个全排列中，从小到大的第n个全排列是多少。
比如求在（1，2，3，4，5）的全排列中，第62个排列组合是34152。[注意具体计算中，要先 -1 才是其康托展开的值。]
另外康托展开也是一个数组到一个数的映射，因此也是可用于hash，用于空间压缩。比如在保存一个序列，我们可能需要开一个数组，如果能够把它映射成一个自然数， 则只需要保存一个整数，大大压缩空间。比如八数码问题。