康托展开学习笔记

1.什么是康托展开

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

简单来说，康托展开就是对于任意一个全排列，求一个自然数与它对应，即一个全排列到一个自然数的映射，这种映射是唯一的。

2.怎么实现康托展开

公式

$ X=\sum_{i=1}^n a_{i}(i-1)! $

其中，\(a_{i}\)代表在这个排列中的第\(i\)个数后面有多少个数比它小。

这个公式求的是当前排列前面有多少个排列

例如，对于排列\(14325\)，它的康托展开是

\(X=0\times(5-1)!+2\times(4-1)!+1\times(3-1)!+0\times(2-1)!+0\times(1-1)!=0+12+2+0+0=14\)

所以\(14325\)前面还有\(14\)个排列，所以\(14325\)是第\(14+1=15\)个排列

本蒟蒻对于这个公式的一些浅显理解:

假设有一个排列\(a_{1},a_{2},···,a_{n}\)

如果其满足\(a_{1} < a_{2}<···< a_{n}\),那么它是第一个排列。所以答案为\(1\)，计算公式之后不难发现公式正确

如果\(a_{2},a_{3},···,a_{n}\)中有比\(a_{1}\)小的数，以这些数为开头的排列必定在\(a_{1}\)为开头的排列前面，所以要加上这些排列数。确定了开头了之后，其后面还有\((n-1)\)个数，可以构成\((n-1)!\)种序列，所以公式第一项为比\(a_{1}\)小的数的个数乘以\((n-1)!\)

以此类推，可以得到该序列的排位。

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N = 110;

long long sum[N];
int a[N] , n , Min[N];

void fc(int n)//预处理阶乘
{
    sum[0] = 1;
    for(int i = 1; i <= n - 1; i ++)
      sum[i] = i * sum[i - 1];
}

void get(int pos)//预处理ai
{
    for(int i = pos + 1; i <= n; i ++)
      if(a[i] < a[pos]) Min[pos] ++;
}

long long cantor()//康托展开
{
    long long ans = 0; 
    for(int i = 1; i <= n; i ++)
      ans += Min[i] * sum[n - i];
    return ans; 
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
   fc(n);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) get(i);
    printf("%lld" , cantor() + 1);
    return 0;
}

3.逆康托展开

知道了如何给定排列求序号，因为排列与序号一一对应，所以自然可以用序号求排列。

逆康托展开其实就是把康托展开反向计算。

假设字典序号为\(pos\)，共有\(n\)个数

首先用\(pos\div(n-1)!\)，余数自然就是$\sum_{i=2}^n a_{i}(n-i)! $,商就是 \(a_{1}\)

如此反复，可求得\(a_{1},a_{2},···,a_{n}\)

例如：给定\(pos=15,n=5\)，所以有\(pos-1=14\)个比它小的序列

\(14\div(5-1)!=0······14,a_{1}=0\)

\(14\div(4-1)!=2······2,a_{2}=2\)

\(2\div(3-1)!=1······0,a_{3}=1\)

\(0\div(2-1)!=0······0,a_{4}=0\)

\(0\div(1-1)!=0,a_{5}=0\)

接下来，在\(1,2,3,4,5\)中，有\(0\)个比它小的数的数是\(1\)，所以第一位为\(1\)

在\(2,3,4,5\)中，有\(2\)个比它小的数的数是\(4\)，所以第二位为\(4\)

在\(2,3,5\)中，有\(1\)个比它小的数的数是\(3\)，所以第三位为\(3\)

在\(2,5\)中，有\(0\)个比它小的数的数是\(2\),所以第四位为\(2\)

第五位为\(5\)

综上，原序列为\(14325\)

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N = 110;

long long sum[N];
int a[N] , n , pos , Min[N];
bool use[N];

void fc(int n)
{
    sum[0] = 1;
    for(int i = 1; i <= n - 1; i ++)
      sum[i] = i * sum[i - 1];
}

void recantor(int pos)
{
    for(int i = n - 1; i >= 0; i --)
    {
        int s = 0;
        Min[n - i] = pos / sum[i] , pos = pos % sum[i];
        for(int j = 1; j <= n; j ++)
        {
            if(! use[j])
              s ++;
            if(s == Min[n - i] + 1)
             {
                a[n - i] = j;
                use[j] = 1;
                break;
            }  
        }
    }
      
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> pos;
    fc(n);
    recantor(pos - 1);
    for(int i = 1; i <= n; i ++)
      cout << a[i];
    return 0;
}

4.例题

P3014[USACO11FEB]牛线Cow Line

P5367【模板】康托展开

康托展开学习笔记

原文：https://www.cnblogs.com/WKAHPM/p/11628872.html