康拓展开

定义：

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

把一个整数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)。

康托展开的最基本应用应该就是，求一个排列（按字典数）的序号（就是第几个）。
而其逆运算就是求序号对应的排列。

康托展开和逆康托展开

康托展开举例

再举个例子说明。
　　在

5个数的排列组合中，计算 34152的康托展开值。

首位是3，则小于3的数有两个，为1和2，

，则首位小于3的所有排列组合为

第二位是4，由于第一位小于4，1、2、3中一定会有1个充当第一位，所以排在4之下的只剩2个，所以其实计算的是在第二位之后小于4的个数。因此

。

第三位是1，则在其之后小于1的数有0个，所以

。

第四位是5，则在其之后小于5的数有1个，为2，所以

。

最后一位就不用计算啦，因为在它之后已经没有数了，所以

固定为0

根据公式：

　　所以比34152小的组合有61个，即34152是排第62。

逆康托展开举例

一开始已经提过了，康托展开是一个全排列到一个自然数的双射，因此是可逆的。即对于上述例子，在

给出61可以算出起排列组合为34152。由上述的计算过程可以容易的逆推回来，具体过程如下：

用 61 / 4! = 2余13，说明

,说明比首位小的数有2个，所以首位为3。

用 13 / 3! = 2余1，说明

，说明在第二位之后小于第二位的数有2个，所以第二位为4。

用 1 / 2! = 0余1，说明

，说明在第三位之后没有小于第三位的数，所以第三位为1。

用 1 / 1! = 1余0，说明

，说明在第二位之后小于第四位的数有1个，所以第四位为5。

最后一位自然就是剩下的数2。

通过以上分析，所求排列组合为 34152。

例题

P2272【康托展开】数字排列

问题描述

{1,2,3} 三个数的全排列可看做6个数字，按从小到大排序得到序列a：123,132,213,231,312,321
下面有两种提问：
1.数字231在序列a中排名第几？回答4
2.数列a中排名第5的数字是多少？回答312

给出n个数字(1,2,3,...,n)，回答关于序列a的1和2两种提问。

输入格式

第一行，两个整数n和m，n表示数字1到n(n<=9)构成的全排列，m(m<=100,000)表示询问数
接下来m行，表示询问，每行两个整数x和y，x=1表示第一种询问，回答y的排名；x=2表示第2种询问，答出排名为y的数字

输出格式

m行，每行一个整数，表示对应的答案。

样例输入

3 2
1 231
2 5

样例输出

4
312

提示

结果巨大，建议用long long 类型

时间限制 : 20000 MS 空间限制 : 65536 KB

代码

 1 #include <stdio.h>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 char ch;
 5 bool flag[15];
 6 long long n, m, x, num;
 7 long long a[15], b[15];
 8 int q[10]= {1,1,2,6,24,120,720,5040,40320,362880};
 9 inline int read()  
10 {
11     int s=0;
12     char c=getchar();
13     while (c<'0' || c>'9') c=getchar();
14     while (c>='0' && c<='9') s=s*10+c-'0',c=getchar();
15     return s;
16 }
17 int kangtuo()
18 {
19     long long i, j, num = 0;
20     num = (a[1] - 1) * q[n - 1];
21     for(i = 2; i <= n; i ++)
22     {
23         long long temp = 0;
24         for(j = 1; j < i; j ++)
25             if(a[j] < a[i])temp ++;
26         num += (a[i] - temp -1) * q[n - i];
27     }
28     return num + 1;
29 }
30 void nikangtuo(int num)
31 {
32     long long i, j, t;
33     num --;
34     for(i = 1; i <= n; i ++)
35     {
36         t = num / q[n - i];
37         for(j = 1; j <= n; j ++)
38             if(!flag[j])
39             {
40                 if(!t)break;
41                 t --;
42             }
43         flag[j] = true;
44         num %= q[n - i];
45         b[i] = j;
46     }
47 }
48 int main()
49 {
50     n=read(),m=read();
51     while(m --)
52     {
53         x=read();
54         if(x == 1)
55         {
56             memset(flag, 0, sizeof(flag));
57             for(int  i = 1; i <= n; i ++)
58             {
59                 cin>>ch;
60                 a[i] = ch - '0';
61             }
62             cout<<kangtuo()<<endl;
63         }
64         else
65         {
66             memset(b, 0, sizeof(b));
67             memset(flag, 0, sizeof(flag));
68             num=read();
69             nikangtuo(num);
70             for(int i = 1; i <= n; i ++)cout<<b[i];
71             cout<<endl;
72         }
73     }
74 }