康托展开

涉及了组合数学的知识，他的定义是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的名次，因此是可逆的。

1. 效果：

   给定一个序列计算比序列组合小的总个数。

   （比如封面图的晓响雷电，给她们标号，可求比该序数排列组合小的拍照顺序总数）

假设有 {1， 2， 3} 这三个数，那么全部的排列组合有 6种，按从小到大的顺序有 123, 132，213， 231， 312， 321。

而康托展开能以O(N^2)求出比某个排序组合小的个数。比如说 比 213 小的数有2个，比312小的数有4个。

2. 原理：

   X = A[0] (n-1)! + A[1] (n-2)! + … + A[n-1] * 0!

   • A[i] 指的是位于位置i后面的数小于A[i]值的个数,后面乘的就是后面还有多少个数的阶乘

   • 这个算出来的数康拖展开值，是在所有排列次序 - 1的值，因此X+1即为在全排列中的次序

例子 ：
在（1，2，3，4，5）5个数的排列组合中，计算 34152的康托展开值。
带入上面的公式

X = 2 4! + 2 3! + 0 2! + 1 1! + 0 * 0!
=>X = 61

什么你上面的有点没看懂？ 不急这有文字描述版~

假设有 {1，2， 3， 4} 这4个数，根据组合数学的知识，一共有 4*3*2*1种排序组合。

比如说3421（且看封面图的晓响雷电，给她们标号为3421，求比3421排序组合小的拍照顺序总数）

• 首位3，比3小的且之前没出现的数有1、2，那么就有2*3！

• 次位4，比四小的数有1、2、3，但已经出现在首位了，所以共有两位，即1、2，那么有2*2！

• 第三位2，比2小的只有1，且首位次位无1，那么就有1*1！

  则 2*3！+2*2！+1*1！就是比3421排序组合小的总个数。

总结：从首位3开始到倒数第二位截至，找出比当前这位数小的个数，且之前没有出现过的数的个数乘以对应阶乘，累加结果就是我们要求的值。

3.用途：

这种技巧也能够运用在状态压缩上面，某个排序组合有 x个比它小的排序组合，那么可以给这种排序组合编号为x，可以保证不会有编号重叠的情况，实现符号压缩。 可以用于前篇的爬虫文件名命名中

逆康托展开

康拖展开是从序列到自然数的映射且是可逆的，那么逆康拖展开便是从自然数到序列的映射
例子 ：
在（1，2，3，4，5) 给出61可以算出起排列组合为34152
具体过程如下：
用 61 / 4! = 2余13，说明 ,说明比首位小的数有2个，所以首位为3。
用 13 / 3! = 2余1，说明 ，说明在第二位之后小于第二位的数有2个，所以第二位为4。
用 1 / 2! = 0余1，说明 ，说明在第三位之后没有小于第三位的数，所以第三位为1。
用 1 / 1! = 1余0，说明 ，说明在第二位之后小于第四位的数有1个，所以第四位为5。

总结：在已知编号的情况下，也能够通过编号还原排列组合。顺序反过来就行了。

代码实现

int cantor(char* ss) { // 先往 n[] 存放阶乘的结果
    int ret = 0;
    for(int i = 0; i < 9; ++i) {
        int cnt = 0;
        for(int j = i+1; j < 9; ++j) {
            if(ss[j] < ss[i]) cnt++;
        }
        ret += cnt*n[8-i];
    }
    return ret;
}

void decantor(int num, char *ss) {
   int p = 0; bool v[10];
   memset(v, false, sizeof(v));
   for(int i = 8; i >= 0; --i) {
        int cnt = 0, tmp = num/n[i];
        num %= n[i];
        for(int j = 0; j < 9; ++j) {
            if(v[j]) continue;
            if(cnt == tmp) {
                ss[p++] = j+'0';
                v[j] = true;
                break;
            }
            cnt++;
        }
   }
   ss[p] = '\0';
}

​