康托展开（Cantor Expansion）

This blog post is only available in Simplified Chinse.

现在有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 个。下面我们枚举验证：

的确是～

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

数学家的凝视

康托展开的逆

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

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

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

将 $k$ 减去 1，此时 $k$ 就代表了比我们要求的排列小的排列有几个（参考前面，我们最后把求出的答案+1了）；
$k$ 除以 $(N-1)!$ ，得到 $A_n$
$k$ 除以 $(N-2)!$ ，得到 $A_{n-1}$
...

以此类推，最终可以求出整个 $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 1: Two space-separated integers: N and K
Lines 2..2K+1: Line 2i and 2*i+1 will contain a single query.

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.

输出格式：

Lines 1..K: Line i will contain the answer to query i.

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：

输出样例#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 - 洛谷博客

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

6/1/2018