康托展开(Cantor Expansion)例题+详解

/ 1评 /

现在有N个数,分别为1到N,如果要问你这些数的所有排列中,从小到大数的第N个是多少,如何求解?

显然当N很小时直接写个模拟就可以了。但是这样写的时间复杂度至少是A_N^N,也就是N!,很容易超时。想想13!已经是6227020800了……有没有更快的方法呢?

题外话

这又让我回想起在 ZS 那里上课的日子……当时做过一道题叫做“Jam的计数法”(洛谷传送门:Jam的计数法),当时ZS并没有介绍康托展开这种高级的方法,只是告诉我们:知道了一个1~N的排列,如何求第一个比它大的排列。想法很简单:从这个排列的最后(即第N个数字)向前寻找,直到找到一个下降的地方,把下降的数字替换掉(当然这有很多方法)。用这种想法可以写暴力,对于洛谷上这题可以拿40分。

康托展开的定义&公式

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

不多说了,直接放公式:

\displaystyle X = A_n * (n-1)! + A_{n-1} * (n-2)! + \dots + A_i * (i-1)! + \dots + A_2 * 1! + A_1 * 0!

其中 A_i 表示这个排列里(从左到右)第 i 个数字之后有多少比这个数字小的数字(看看下面的例子就明白了~)。

这个公式可以求出某个具体的 1~N 排列在所有 1~N 排列中排第几个。举个例子:1~5的排列,1 3 2 5 4 排在第几个呢?首先看看:第一个数字 1 之后没有比 1 小的数字,所以 A_n = 0 ;在3之后有一个比它小的(2),所以 A_{n-1} = 1 。依此类推:

\displaystyle 0 * (5-1)! + 1 * (4-1)! + 0 * (3-1)! + 1 * (2-1)! + 0 * (1-1)! = 7

比这个排列还要小的排列有 7 个,所以它排在第 8 个。下面我们枚举验证:

1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
1 2 5 4 3
1 3 2 4 5
1 3 2 5 4

的确是~

话说康托尔(Cantor)这位数学家似乎也是个大佬,原来我们还做过一道题叫做“Cantor表”,就是他的杰作(虽然那题很简单)。就是下面这位大佬!

数学家的凝视

康托展开的逆

现在我们可以求一个 1~N 的排列在所有 1~N 的排列里从小到大是第几个了,那么如果我们知道一个数字 k,想知道 1~N 的排列里第 k 个排列是什么,怎么办呢?

当然可以用二分,时间复杂度大概 log_2 (N!)。但是既然前面说了“康托展开是一个全排列到一个自然数的双射”,“是可逆的”,所以我们不妨试试求康托展开的逆,可以做到 O(N) ~

康托展开的逆并不复杂,相当于把刚刚的那个等式倒过来做。比如我们要求 1~N 的排列里第 k 大的,步骤如下:

  1. k 减去 1,此时 k 就代表了比我们要求的排列小的排列有几个(参考前面,我们最后把求出的答案+1了);

  2. k 除以 (N-1)!,得到 A_n

  3. k 除以 (N-2)!,得到 A_{n-1}

  4. ...

以此类推,最终可以求出整个 A 数组,从而推出这个排列。

例题

洛谷 P3014 [USACO11FEB]牛线 Cow Line

题目描述

The N (1 <= N <= 20) cows conveniently numbered 1...N are playing yet another one of their crazy games with Farmer John. The cows will arrange themselves in a line and ask Farmer John what their line number is. In return, Farmer John can give them a line number and the cows must rearrange themselves into that line.

A line number is assigned by numbering all the permutations of the line in lexicographic order.

Consider this example:

Farmer John has 5 cows and gives them the line number of 3.

The permutations of the line in ascending lexicographic order: 1st: 1 2 3 4 5

2nd: 1 2 3 5 4

3rd: 1 2 4 3 5

Therefore, the cows will line themselves in the cow line 1 2 4 3 5.

The cows, in return, line themselves in the configuration '1 2 5 3 4' and ask Farmer John what their line number is.

Continuing with the list:

4th : 1 2 4 5 3

5th : 1 2 5 3 4

Farmer John can see the answer here is 5

Farmer John and the cows would like your help to play their game. They have K (1 <= K <= 10,000) queries that they need help with. Query i has two parts: C_i will be the command, which is either 'P' or 'Q'.

If C_i is 'P', then the second part of the query will be one integer A_i (1 <= A_i <= N!), which is a line number. This is Farmer John challenging the cows to line up in the correct cow line.

If C_i is 'Q', then the second part of the query will be N distinct integers B_ij (1 <= B_ij <= N). This will denote a cow line. These are the cows challenging Farmer John to find their line number.

输入输出格式

输入格式:

Line 2*i will contain just one character: 'Q' if the cows are lining up and asking Farmer John for their line number or 'P' if Farmer John gives the cows a line number.

If the line 2*i is 'Q', then line 2*i+1 will contain N space-separated integers B_ij which represent the cow line. If the line 2*i is 'P', then line 2*i+1 will contain a single integer A_i which is the line number to solve for.

输出格式:

If line 2*i of the input was 'Q', then this line will contain a single integer, which is the line number of the cow line in line 2*i+1.

If line 2*i of the input was 'P', then this line will contain N space separated integers giving the cow line of the number in line 2*i+1.

输入输出样例

输入样例#1:

5 2 
P 
3 
Q 
1 2 5 3 4 

输出样例#1:

1 2 4 3 5 
5 

参考代码

这里贴的就是刚刚那题AC的代码。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=25;
int n,m,a[maxn],b[maxn];
bool vis[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline long long llread(){
    long long ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*(long long)10+(long long)(ch-'0'),ch=getchar();
    return (long long)ret*f;
}
inline char read_ch(){
    char ch=getchar();
    while (ch!='P'&&ch!='Q') ch=getchar();
    return ch;
}
inline bool check(int L,int R){
    for (int i=L;i<=R;i++) if (vis[i]) return 1;
    return false;
}
int main(){
    n=read();m=read();
    for (int k=1;k<=m;k++){
        char ch=read_ch();
        if (ch=='Q'){
            long long fac=1;
            for (int i=1;i<=n;i++) a[i]=read(),fac=fac*(long long)i;
            fac=(long long)fac/(long long)n;
            long long x=0;int cnt=n-1;
            for (int i=1;i<=n;i++){
                int now=0; //now表示这个排列里(从左到右)第i个数字之后有多少比这个数字小的数字
                for (int j=i+1;j<=n;j++) if (a[i]>a[j]) now++;
                x=(long long)x+(long long)now*(long long)fac;
                if (cnt) fac=(long long)fac/(long long)cnt--;
            }
            printf("%lld\n",++x);
        } else if (ch=='P'){
            long long x=llread();x--;long long fac=1;
            for (int i=2;i<n;i++) fac=fac*(long long)i;
            for (int i=n;i>=1;i--){
                a[n-i+1]=(long long)x/fac;
                x%=fac;
                if (i-1) fac=fac/(long long)(i-1); else fac=1;
            }
            memset(vis,0,sizeof(vis));
            for (int i=1;i<=n;i++){ //B[i]即i位上的数字 
                int cnt=0;b[i]=-1;
                for (int j=0;j<=n;j++){
                    if (vis[j]) cnt++;
                    if ((!vis[cnt+a[i]+1])&&(!check(j+1,cnt+a[i]))){
                        vis[cnt+a[i]+1]=1;b[i]=cnt+a[i]+1;break;
                    }
                }
            }
            for (int i=1;i<n;i++) printf("%d ",b[i]);printf("%d\n",b[n]);
        }
    }
    return 0;
}

参考

康托展开 - 维基百科,自由的百科全书

康托展开_百度百科

康托展开详解 | Comzyh的博客

题解 P3014 【[USACO11FEB]牛线Cow Line】 - YoungNeal的Blog - 洛谷博客

想不到吧,隔了这么长时间我居然更新博客了~


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/cantor-expansion/


一条回应:“康托展开(Cantor Expansion)例题+详解”

  1. ZigZagK说道:

    Dalao更新Blog了好稳啊Orz

发表评论

电子邮件地址不会被公开。 必填项已用*标注