Cantor序列

作用：当一组数字唯一时。每一种排列在全排列中的序号唯一，Contor
求的就是当前序列在全排列中的序号。

Cantor展开式：

X=an(n-1)!+an-1(n-2)!+…+ai(i-1)!+…+a21!+a1*0!

使用示例来帮助理解利用Cantor展开如何求解本问题。
假如序列s=[“A”,”B”,”C”,”D”]
需要求序列s’=[“D”,”A”,”B”,”C”]是序列s的全排列中的第几个排列，记作X(s’);

X(s’) = 3（在序列DABC中有3个比D小）*3!+ 0（在剩下的序列ABC中有0个比A小）*2！+ 0（在剩下的序列BC中有0个比B小）*1！+ 0（在剩下的序列C中有0个比C小）*0！ =18

那么序列 s’是 s 的全排列中第18个排列（从0开始计数）；
同理可以根据 s 算第18个排列序列。

总结：康托展开是一个全排列到一个自然数的一一映射

正向展开：

//value数组存放当前排列   
const int fac[]={1,1,2,6,24,120,720,5040,40320};//康托序列   
inline int cantor(){  
    int ans=0;  
    for(int i=0;i<N;i++)  
    {  
        int cnt=0;  
        for(int k=i+1;k<N;k++)  
        {  
            if(value[k]<value[i])  
                cnt++;  
        }  
        ans+=fac[8-i]*cnt;  
    }  
    return ans;  
}

反向展开：

//value数组存放当前排列   
const int fac[]={1,1,2,6,24,120,720,5040,40320};//康托序列   
inline int cantor(Point p){  
    int ans=0;  
    for(int i=0;i<N;i++)  
    {  
        int cnt=0;  
        for(int k=i-1;k>=0;k--)  
        {  
            if(value[k]>value[i])  
                cnt++;  
        }  
        ans+=fac[i]*cnt;  
    }  
    return ans;  
}