康托展开学习模板

定义：

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

康托展开的用法：

　　有一个以元素{1,2,...,n}为排列元素的全排列：

　　1. 给定一个全排列序列，求该序列是所有全排列序列中字典序第几的序列

　　2. （逆康托展开）给定全排列大小n,字典序k,求字典序为k的排列

公式及原理：

　V = A[0]*(n-1)! + A[1]*(n-2) +...+ A[n-1]*0!

　* A[i]对应的是位于位置i后的数的个数，乘(n-i-1)的阶乘

　V的值对应上述康托展开的用法中序列的康托展开值，也就是字典序排名

听不懂在说什么？没事，让我们看看下面的例子

例：

　　在给定的序列{1,2,3,4,5,6}组成的全排列中,计算3 5 6 2 1 4对应的康托展开值

　　* V = 2*5! + 3*4! + 3*3! + 1*2! + 0*1! + 0*0!

　　　　= 240 + 72 + 18 + 2 + 0 +0

　　　　= 332

　　ps：求得的康托展开值是从0开始的，也就意味着 V+1才是相应的排列在原序列中的字典序排名

康托展开代码：

 1 int cantor(int *a,int n) {  ///a[]:原数组,下标从1开始
 2     int ans=0;
 3     for(int i=1;i<n;i++) {
 4         int m=1,rk=0;
 5         for(int j=i+1;j<=n;j++) {
 6             if(a[j]<a[i])
 7                 rk++;
 8             m*=(j-i);   ///阶乘
 9         }
10         ans+=rk*m;      ///据公式X = A[0] * (n-1)! + A[1] * (n-2)! + … + A[n-1] * 0!
11                         ///A[i] = rk
12     }
13     return ans+1;       ///ans+1,即为原序列在全排列中的次序
14 }

View Code

逆康托展开：

给定全排列大小n,字典序k,求字典序为k的排列

例：

　　在{1,2,3,4,5,6}中给出字典序排名为666可以算出排列组合为6 3 4 5 2 1

　　具体过程：

　　666 - 1 = 665;

　　665 / 5! = 5 余 65 说明首位排名第 6 ，即首位为6；

　　 65 / 4! = 2 余 17 说明第二位排名第 3 ，即第二位为3；

　　 17 / 3! = 2 余 5 说明第三位排名第 3 ，即第三位为4；

　　 5 / 2! = 2 余 1 说明第四位排名第 3 ，即第四位为5；

　　　 1 / 1! = 1 余 0 说明第五位排名第 1 ，即第五位为2；

　　　最后一位即为剩下的1。

逆康托展开代码：

 1 void decantor(int x,int n,int *a) {
 2     bool vis[10];
 3     memset(vis,false,sizeof(vis));
 4     for(int i=0;i<n;i++) {
 5         int rk=x/f[n-i-1];
 6         for(int j=0;j<=rk;j++)      ///与上述同理,已访问过的数不在序列中，所以要将rk++
 7             if(vis[j]) rk++;
 8         a[i]=rk+1;          ///求得的rk是比A[i]小的数的个数，所以A[i]=rk+1
 9         vis[rk]=true;
10         x%=f[n-i-1];
11     }
12 }

View Code

下面给出完整代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 int f[]={1,1,2,6,24,120,720,5040,40320,362880}; ///算出1-9的阶乘，0的阶乘用1代替
 6 int cantor(int *a,int n) {
 7     int ans=0,rk;
 8     for(int i=1;i<n;i++) {
 9         rk=0;
10         for(int j=i+1;j<=n;j++)   ///计算位于i后面的数小于a[i]的个数,rk即为i的排名
11             if(a[j]<a[i])
12                 rk++;
13         ans+=rk*f[n-i];     ///据公式X = A[0] * (n-1)! + A[1] * (n-2)! + … + A[n-1] * 0!
14                             ///A[i] = rk
15     }
16     return ans+1;           ///ans+1,即为原序列在全排列中的次序
17 }
18 void decantor(int x,int n,int *a) {
19     bool vis[10];
20     memset(vis,false,sizeof(vis));
21     for(int i=0;i<n;i++) {
22         int rk=x/f[n-i-1];
23         for(int j=0;j<=rk;j++)      ///与上述同理,已访问过的数不在序列中，所以要将rk++
24             if(vis[j]) rk++;
25         a[i]=rk+1;          ///求得的rk是比A[i]小的数的个数，所以A[i]=rk+1
26         vis[rk]=true;
27         x%=f[n-i-1];
28     }
29 }
30 int main()
31 {
32     int t,n,oper,a[11],v;
33     cin>>t;
34     while(t--) {
35         cin>>oper;
36         if(!oper) {
37             cin>>n;
38             for(int i=1;i<=n;i++)
39                 cin>>a[i];
40             cout<<cantor(a,n)<<endl;
41         }
42         else {
43             cin>>n>>v;
44             decantor(v-1,n,a);
45             for(int i=0;i<n;i++)
46                 cout<<a[i]<<' ';
47             cout<<endl;
48         }
49     }
50     return 0;
51 }

View Code