康托(Cantor)展开与逆展开理解与运用

比如，有一个1~5的排列，现在需要计算2, 5, 4, 3, 1这一排列P按字典序排序的排名。那么可以将其转化为计算按字典序在该排列前面一共有多少个排列。（比较排名？e.g.：对于排列1, 2, 3, 4, 5与2, 5, 4, 3, 1，显而易见，因为两者第一个元素前者比较小，所以前者字典序比较小，所以排名应在后者前面。我们可以通过比较相同位置的元素的大小来确定排名的先后）

所以，我们先由排列P(2, 5, 4, 3, 1)的第一个元素开始依次往后看。

对于第一个元素2，我们可以知道别的第一个元素<2 的排列字典序一定是小于排列P的；所以1~5中，1 < 2，既当前位置有1这一种可能使该排列的字典序小于P，后面还有4个元素，这4种元素的排列总数为 $4!$ ，因为前面有1种可能，所以这里可以得到 $1*4!$ 个排列字典序小于P
继续向下一位看。在1~5中排除掉刚刚已经在第一个位置的2（前面出现过了后面不可能再出现），就是在（1, 3, 4, 5）中，有（1, 3, 4) < 5，这里有3种可能，后面3个元素共有 $3!$ 个排列，所以这里又可以得到 $3*3!$ 个排列字典序小于P
同理，下一位有 (1, 3) < 4（上面使用过2，故不算）, 后面剩余2位，可以得到 $2 * 2!$ 个排列
下一位：有1 < 3 ，后面剩1位，得到 $1*1!$
最后一位：（无元素） < 1 ，后面剩0位，得到 $0*0!$

总结一下：刚刚得到字典序小于P(2, 5, 4, 3, 1)的排列个数

$X=1*4!+3*3!+2*2!+1*1!+0*0!=47$

但这里需要注意：现在我们求的是按字典序排序下在排列P之前有几个排列，我们原先要计算的是排名，所以要加上1，得 $X=48$ 。

公式

上面举例过一遍了，下面的公式应该很好理解吧，就不细说了

$X=a_{1}(n-1)!+a_{2}(n-2)!+...+a_{i}(n-i)!+...+a_{n-1}\cdot1!+a_{n}\cdot0! + 1$

其中：

${a_i}$ 表示比第 $i$ 位上的元素字典序小且没使用过的元素个数

$n$ 既排列元素的个数

$X$ 是排列的排名

完整定义

………………引自Zhihu user---我不玩了给我退学

（这里说排名从0开始，建议计算后手动加1.比较符合“排名”，更形象，加不加也无所谓啦）（看不看无所谓，知道基本意思就行了）

C++代码

代码实现

//计算阶乘
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

//康托展开函数
int cantorExpansion(const vector<int>& p){
    int n = p.size();
    int x = 0;
    //计算康托展开的每一位
    for(int i = 0; i < n - 1;i++){
    	//smc:smaller_count
        int smc = 0;
        for(int j = i + 1; j < n;j++){
            if (p[j] < p[i]){
                smc++;
            }
        }
        x += smc * factorial(n - i - 1);
    }

    return x;
}

上面这样写比较直观；当然可以省去factorial函数，像下面这样（也就只改了个x的计算）

int cantorExpansion(const vector<int>& p){
	int n = p.size();
    int x = 0;
    for(int i = 0; i < n - 1;i++){
        int smc = 0;
        for(int j = i + 1; j < n;j++){
            if(p[j] < p[i]){
                smc++;
            }
        }
        x = (x + smc) * (n - i - 1);
    }
    return x;
}

（可能有些看官不理解第二段代码计算x的部分，这里解释一下：x+smc会累加的smc并乘上下一位对应的位数（也就是这一位阶乘的最高位），下一次一并计算，上次只乘了阶乘的最后一位的smc会再乘阶乘的下一位，直到都乘过了。光说可能有点抽象，下面模拟以下全排列1~5在此函数下X的计算过程（ ${a_i}$ 表示比第 $i$ 位上的元素字典序小且没使用过的元素个数）：

$X=((((a_1*4)+a_2)*3+a_3)*2+a_4)*1$