哈希 — 康托展开

http://blog.csdn.net/fuyukai/article/category/2898321/1  图论、次小生成树，差分约束，双连通

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

全排列： 1，2，3三个数的全排列： 
1,2,3 
1,3,2 
2,1,3 
2,3,1 
3,1,2 
3,2,1 
总共 3! = 6种。 
但是我们用一些数或数组来表示当前排列的顺序时，往往是用的 3^3 = 9 的存储空间，当不同的数数量较多的时候，空间浪费会非常大，所以，我们需要康托展开。

举例： 
3 5 7 4 1 2 9 6 8 展开为 98884。（实际为第98885个） 
因为X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884

思路： 
我们从上面例子的可以看出，第一个数是3，他后面有8个数，比3小的有2个，说明以三开头的第一个排列前面有2*8!个，类似的，5这个数字，之前的3*7!，所以可以打出代码：

int factor[]={1,1,2,6,24,120,720,5040,40320,362880};        //各数的阶乘……
int cantor(){
    int sum=0;
    for(int i=0;i<n;i++)
    {
        int cnt=0;
        for(int j=i+1;j<n;j++)
            if(tmp[j]<tmp[i])      //tmp数组表示排列
                cnt++;
        sum+=cnt*factor[n-i-1];
    }
    return sum+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
3
4
5
6
7
8
9
10
11
12
13

康托展开的逆运算 
康托展开是一个双射，那么，自然就存在逆运算，举个例子： 
如n=5,x=96时： 
首先用96-1得到95，说明x之前有95个排列.(将此数本身减去！) 
用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. 
（来自维基百科）

代码如下：

void inv_cantor(int num)
{
    num--;
    memset(v,0,sizeof(v));
    for(int i=0;i<n;i++)
    {
        int index=num/factor[n-i-1],j=1;
        for(j=1;j<=n;j++)
            if(!v[j])
            {
                if(!index)
                    break;
                index--;
            }
        tmp[i]=j,v[j]=1;
        num%=factor[n-i-1];
    }
}