康托展开与逆康托展开(模板)

51 阅读 0 评论 34 点赞

我是靠谱客的博主舒心人生，最近开发中收集的这篇文章主要介绍康托展开与逆康托展开(模板)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

康托展开：

求一个数在全排列中的第几位。
例如{1,2,3,4,…,n}表示1,2,3,…,n的排列，12345……n，即为第0个排列。
以{1,2,3,4} 表示1，2，3，4的排列为例，求1324在全排列中的第几位。
由组合数学易得：全排列的总数为4!。
第一位有4种选法，第二位3种，第三位2种，第一位1种。
首先 1 比它小的数是 0 个，比1000小的排列有0 * 3！（3！代表后面3个数的全排列个数）
其次 3 比它小的数有1，2。但1已经在前面出现过了，所以比1300小的排列有 1*2！。
然后 2 比它小的数有 1。但1已经出现过了，所以比1320小的排列有
0*1！。
最后 4 比它小的数有1，2，3，但都已经出现过了，所以没有比1324
0*3！+1*2！+0*1！ = 2.
排在第二位
1234
1243
1324

完整的公式如下：

把一个整数X展开成如下形式：
X=a[n](n-1)!+a[n-1](n-2)!+…+a[i]*(i-1)!+…+a[2]*1!+a[1]*0![1]
其中a[i]为当前未出现的元素中是排在第几个（从0开始），并且0<=a[i]

逆康托展开：

既然可以求一个数在排列中的第几个，那么反过来也可以求在排列中第i个数是多少。

例如以 {1,2,3,4,5}的排列为例，求第96个数。
首先96-1 = 95(因为是从0开始计数)
95 / 4! = 3 余 23。可知比它小的数有3个，即为 4.
23 / 3! = 3 余 5 。可知比它小的数有 3 个，因为4已经出现过，所以为5.
5 / 2! = 2 余 1 。可知比它小的数有 2 个，即为 3.
1 / 1! = 1 余 0 。可知只有 2 符合
1 / 0! = 0。可知只有 1 符合。
最终结果为45321。
注意：为什么除以4！就可以算出有几个数比它小呢？
因为： 3*4！+3*3！+2*2！+1*1！+0*0! = 95。

95 / 4! = 3 余 3*3！+2*2！+1*1！+0*0!
这里会有疑问，3*3！+2*2！+1*1！+0*0!难道不会大于等于4！吗？

不会的，这里简单的做个比较

(3！+2！+1！+0!)*x > 4 !
x > 2.4。

然而总共只有5个数，3！最多对应3，2！最多对应2，1的阶乘1，0的阶乘0（此处都不用考虑4的阶乘对应的值），（3+2+1+1） < 2.4*4
所以 3*3！+2*2！+1*1！+0*0!肯定 < 4!。
6位数7位数也是一样的，也都无法满足，具体证明可能需要用到数学归纳法（太博大精深，菜鸡不会QAQ)

具体模板：

//预处理阶乘值
int fac[20];
void factor(){
    fac[0] = fac[1] = 1;
    for(int i = 2; i < 13; ++i)
        fac[i] = fac[i-1]*i;
}
//逆康托
string uncantor(int x, int k) {
    string res;
    int i, j, l, t;
    bool h[100]={0};
    for (i = 1; i <= k; i++) 
    {
        t = x / fac[k - i];
        x -= t * fac[k - i];
        for (j = 1, l = 0; l <= t; j++)
            if (!h[j])
                l++;
        j--;
        h[j] = true;
        res += j + '0';
    }
    //康托
 int cantor(int* a,int len){

    int ans = 0;
    for(int i = 0; i < len; ++i){
        int t = 0;
        for(int j = i+1; j < len; ++j){
            if(a[j] < a[i]) t++;
        }
        //cout << t << endl;
        ans += fac[len-i-1]*t;
    }
    return ans+1;//第几个数
}