康托展开：

给定一个排列（由n个数排列而成），我们可以计算出该排列在由n个数组成的所有排列中排名第几（按字典序），这就是康托展开。

比如由4个数1,2,3,4组成排列

那么2413在所有的排列中排第几呢？

首先计算第一位数字比2小的排列有多少种，即 1 * fac[3],怎么得来的呢？首先比2小的数字只有1个，那么第一位数字只有一种选择，剩下的三位数字有fac[3]种选择，所以是1 * fac[3]

现在当第一位固定是2，那么来计算第二位数字比4小的排列有多少种呢？首先比4小的数字有1个，那么第一位数字只有一种选择，剩下的两位数字有fac[2]中选择，所以是1*fac[2]

依次类推，当前两位固定为24,第三位比1小的排列有0 * fac[1]

以此类推，当前两三位固定为241时，第4位比3小的排列有0*fac[0];

即fac[3] + fac[2] = 8;特别记住，我们算出来的是比2413小的排列有多少种，所以2413在所有由1,2,3,4组成的排列中排名第9。

 1 int KT(int *a, int n)//算出数组中存储的数字在全排列中排第几 2 { 3     int i,j,cnt,pos = 0; 4     for(i=0; i<n; ++i) 5     { 6         cnt = 0; 7         for(j=i+1; j<n; ++j) 8             if(a[j] < a[i]) 9                 cnt++;10         pos += cnt * fac[n-i-1];11     }    12     return pos + 1;13 }

View Code

康托逆展开：

给定5个数1,2,3,4,5，  找出排第48的排列是什么，设这个排列为x1x2x3x4x5,

设比x1小的数字有k1个，那么有k1*4!种排列比x1x2x3x4x5小

设比x2小的数字有k2个，那么有k2*3!种排列比x1x2x3x4x5小。

以此类推，共有k1*4!+k2*3!+k3*2!+k4*1!种阶乘比x1x2x3x4x5小

即k1*4!+k2*3!+k3*2!+k4*1!==48-1

而且，k1<=4, k2<=3,k3<=2,k4<=1.那么即使k2,k3,k3取最大值，即k2=3,k3=2,k4=1

那么k2*3!+k3*2!+k4*1! 依旧<4!   所以可以用47/4!得到k1

然后 (47-k1*4!) / 3!  得到k2,

以此类推得到k3,k4

 1 /* 2 算出由数组中存的n个不同的数组成的排第pos位的排列是什么 3 */ 4 void KT_decode(int *a, int *b,int pos, int n) 5 { 6     sort(a,a+n); 7     int i=0,j,cnt1,cnt2; 8     pos -= 1; 9     while(pos)10     {11         cnt2 = 0;12         cnt1 = pos / fac[n-i-1];13         pos -= cnt1 * fac[n-i-1];14         for(j=0; j<n; ++j)15         {16             if(!vis[a[j]])17                 cnt2++;18             if(cnt2==cnt1+1)19             {20                 vis[a[j]] = true;21                 b[i++] = a[j];22                 break;23             }                24         }    25     }26     for(j=0; j<n; ++j)27         if(!vis[a[j]])28             b[i++] = a[j];29     30 }

康托展开和逆展开