康托展开

康托展开公式：

把一个整数X展开成如下形式：

X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!

其中，a为整数，并且0<=a[i]<i(1<=i<=n)

应用：

{1,2,3,4,...,n}表示1,2,3,...,n的排列

如 {1,2,3} 按从小到大排列一共6个。分别是是s1{1, 2, 3} s2{1, 3, 2} s3{2, 1,,3} s4{2, 3, 1} s5{3, 1, 2} s6{3, 2, 1} 。

康托展开就是要把10进制数与与其中的排列一一对应起来。

那么s3{2, 1, 3}的康托展开式是什么呢。

因为{1,2,3}有三个数字,所有n = 3,则s2的可以用康托展开式表示为：

X(s3) = a3 * (2)! + a2 * (1)! + a1 * (0)!;

只要求出a3,a2,a1即可，就是s2中对应数字在排列{1,2,3}中是第几个小的数，也就是出数字本身比它数还小的个数。

2在{2, 1, 3}比它小的只有数字1，所以a3 = 1，

1在{1, 3}比它小的数字没有，所以a2 = 0，(2已经计算)，

3在{3}比它小的数字也没有，所以a1 = 0。(1,2，已经计算过)

所以：X(s3) = 1 * (2)! + 0 * (1)! + 0 * (0)! = 2;

依次可得：
X(s1) = 0 * (2)! + 0 * (1)! + 0 * (0)! = 0;

X(s2) = 0 * (2)! + 1 * (1)! + 0 * (0)! = 1;

X(s3) = 1 * (2)! + 0 * (1)! + 0 * (0)! = 2;

X(s4) = 1 * (2)! + 1 * (1)! + 0 * (0)! = 3;

X(s5) = 2 * (2)! + 0 * (1)! + 0 * (0)! = 4;

X(s6) = 2 * (2)! + 1 * (1)! + 0 * (0)! = 5;

 

知道了X康托展开通过辗转相除法就可以求出对应排列，

比如：X(s5) = 4。

则a3 = 4 / (2)! = 2, 余数为0，

   a2 = 0 / (1)! = 0, 余数为0,

　a1 = 0 / (0)! = 0, 余数为0。

通过康托展开就可以得到全排列。

康托展开代码:

#define ll long long
ll fac[]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘表
ll cantor(int s[], int n)
{
    int i, j, t;
    ll result = 0;
    for (i = 0; i < n - 1; i++)//最后一个可以不用计算 
    {
        t = 0;//比s[i]小的个数 
        for (j = i + 1; j < n; j++)
            if (s[i] > s[j])
                t++;
        result += t * fac[n - i -1];
    }
    return result;
}

康托逆展开代码:

ll cantorInverse(ll result, int s[], int n)
{
    int i;
    for (i = n - 1; i >= 0; i--)
    {
        s[i]  = result / fac[i];
        result %= fac[i];  
    }
}