康托展开

问题解决：求一个n位的全排列按字典序升序排序的位置

例如一个n位排列 2 3 4 1,我们用rank来代表他的排位

从第一位开始：比2小的且没出现在之前的数有: 1 ,那么他对答案带来的贡献自然是 3!

rank += 3!  rank = 6;

第二位(注意，这时第一位已经确定是2了):比3小的且没出现在之前的数有: 1. =>2!

rank += 2! rank = 8;

第三位:比4小的且没出现在之前的数为 1. => 1!

rank += 1! rank = 9;

最后一位不用计算，因为前面n-1位已经确定了以后最后一位就唯一确定了。

这时候，rank的含义还是，这个排列之前有多少个排列 . rank + 1之后才是他实际的位置.

推出普适的式子:


a[i]代表第i位之后小于第i位的数的个数.

请注意：从右到左,i从小到大递增.

逆康托展开

我们可以看出，一个排列和一个整数是一一映射的，又称双射。也就是说，一个排列能唯一确定一个整数，那么显然一个整数也一定能唯一确定一个排列。也就是说，一定有一种方法使一个整数转化为一个排列！这种方法就叫做逆康托展开

例如: 已知2 3 4 1 的rank = 9,我们现在尝试用9还原这个排列。

9/3! = 1 ... 3  代表第一位有一个数小于原数， 显然这个数就是2；第一位的数确定了，取余数继续运算.

3/2! = 1 ... 1 代表第二位有一个数小于原数（同时，这个数也不能在之前出现过哦！）,显然这个数就是3,

1/1! = 1 ... 0 .代表第三个数有一个数小于原数,显然这个数就是4.

第四位唯一确定，不用计算.


代码实现：

暴力 n^2 很容易实现，n过大时我们考虑引入高级数据结构进行优化

康托展开：实质上就是维护一个树状数组就OK

逆康托展开：维护一个单点修改的权值线段树，每次求第k大就好。也可以树状数组+二分.O(nlognlogn)

注：由于阶乘很大，所以逆康托展开不会太大 20! ≈ 2e18

具体应用:

主要的应用就是将一个排列压缩成一个整数储存。可以应用于BFS求八数码问题里


模板:

暴力康托展开:

int str[105];

int fact[105];

void init_fact(int n)

{

    fact[0] = 1;

    for (int i = 1 ; i <= n ; i++) fact[i] = fact[i - 1] * i;

}

int Contor(int str[],int n) // str从1开始储存

{

    int ans = 0;

    for(int i = 1; i <= n; i++)

    {

        int cnt = 0;

        for(int j = i+1; j <= n; j++)

        {

            if(str[i] > str[j])

                cnt++;

        }

        ans += cnt*fact[n-i];

    }

    return ans + 1;

}

暴力逆康托展开:

void deContor(int str[], int n, int x) //第x大数字序列（从0开始），1-n排列.str从1开始存储

{

    int i, j;

    int cnt;

    bool visited[100];

    memset(visited , 0 , sizeof visited);

    for(i = n-1; i >= 0; i--)

    {

        int consult = x/fact[i];        //每一项的系数

        x -= consult*fact[i];          //余数

        for(j = 0, cnt = 0; cnt <= consult; j++)

        {

            if(!visited[j+1])              //未被使用的数字中，第consult大的数字

                cnt++;

        }

        visited[j] = true;                //标记第consult大的已经被使用

        str[n - i] = j;

    }

}