康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

公式

设排列为 $p_n, p_{n-1}, ..., p_1$ , 则

$X = a_n(n-1)! +a_{n-1}(n-2)! +\cdots+a_1\cdot{}0!$

其中 $a_i$ 为 $1 \sim n$ 中除去 $p_n, p_{n-1}, ..., p_{i+1}$ 后比 $p_i$ 小的数的个数.

逆运算

康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出 $1\sim{n}$ 的全排列中第 $X$ 大排列。

首先用96-1得到95，说明x之前有95个排列.(将此数本身减去1)

用95去除4! 得到3余23，说明有3个数比第1位小，所以第一位是4.

用23去除3! 得到3余5，说明有3个数比第2位小，所以是4，但是4已出现过，因此是5.

用5去除2!得到2余1，类似地，这一位是3.

用1去除1!得到1余0，这一位是2.

最后一位只能是1.

所以这个数是45321.

一个参考的实现

int  fac[] = {1,1,2,6,24,120,720,5040,40320};
//康托展开的逆运算,{1...n}的全排列，中的第k个数为s[]
void reverse_kangtuo(int n,int k,char s[])
{
    int i, j, t, vst[8]={0};
    --k;
    for (i=0; i<n; i++)
    {
        t = k/fac[n-i-1];
        for (j=1; j<=n; j++)
            if (!vst[j])
            {
                if (t == 0) break;
                --t;
            }
        s[i] = '0'+j;
        vst[j] = 1;
        k %= fac[n-i-1];
    }
}
// --------------------- 
// 作者：ltree98 
// 来源：CSDN 
// 原文：https://blog.csdn.net/lttree/article/details/24798653 
// 版权声明：本文为博主原创文章，转载请附上博文链接！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 康托展开

# 公式

# 逆运算

康托展开

公式

逆运算