康托展开

康托展开公式:
把一个整数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。
通过康托展开就可以得到全排列。
康托展开代码:
康托展开
 1 #define ll long long
 2 ll fac[]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘表
 3 ll cantor(int s[], int n)
 4 {
 5     int i, j, t;
 6     ll result = 0;
 7     for (i = 0; i < n - 1; i++)//最后一个可以不用计算 
 8     {
 9         t = 0;//比s[i]小的个数 
10         for (j = i + 1; j < n; j++)
11             if (s[i] > s[j])
12                 t++;
13         result += t * fac[n - i -1];
14     }
15     return result;
16 }
康托展开

康托逆展开代码:

康托展开
1 ll cantorInverse(ll result, int s[], int n)
2 {
3     int i;
4     for (i = n - 1; i >= 0; i--)
5     {
6         s[i]  = result / fac[i];
7         result %= fac[i];  
8     }
9 }
康托展开

 

康托展开

上一篇:Stopwatch的使用


下一篇:推荐一些socket工具,TCP、UDP调试、抓包工具