康托展开

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

以下称第$x$个全排列是都是指由小到大的顺序。

可以将一个$1, 2, \ldots, n$的排列，映射到$0, 1, 2, \ldots, n! - 1$中的一个整数。

正变换

已知排列$p_1, p_2, \ldots, p_n$，映射到整数$X$。

$$X = a_1 (n-1)! + a_{2}(n-2)! + \cdots + a_{n} 0!$$

$a_i$表示小于$p_i$的数字，在$p_1, p_2, \ldots, p_{i-1}$中没出现的个数。

显然$0 \leq a_i \leq n - i$。

例子：
$\{p_i\} = {3, 5, 7, 4, 1, 2, 9, 6, 8}$
对应的
$\{a_i\} = {2, 3, 4, 2, 0, 0, 2, 0, 0}$
最终
$X = 2 \times 8! + 3 \times 7! + 4 \times 6! + 2 \times 5! + 0 \times 4! + 0 \times 3! + 2 \times 2! + 0 \times 1! + 0 \times 0! = 98884$
即有$98884$个排列小于$\{a_i\}$。

第一个排列${1, 2, \ldots, n}$对应的康托展开是$0$。
最后一个排列${n, n - 2, \ldots, 1}$对应的康托展开是$n! - 1$。

// 将全局变量a数组中的排列映射到整数
int encode() {
	int v[10] = {};
	int re = 0;
	for (int i = 0; i < 9; i++) {
		int cnt = 0;
		for (int j = 0; j < a[i]; j++) {
			if (v[j] == 0) {
				cnt++;
			}
		}
		v[a[i]] = 1;
		re += cnt * fac[8 - i];
	}
	return re;
}

逆变换

首先根据最终的$X$计算出数组$\{a_i\}$。
$$a_i = \left\lfloor \frac{X \bmod ((n - i + 1)!)}{(n - i)!} \right\rfloor$$
然后根据数组$\{a_i\}$计算出排列$\{p_i\}$。

// 将整数映射到全局变量a数组中的排列
void decode(int x) {
	int v[10] = {};
	for (int i = 0; i < 9; i++) {
		int cnt = x % fac[9 - i] / fac[8 - i];
		for (int j = 0; j < 9; j++) {
			if (v[j] == 0) {
				if (cnt == 0) {
					a[i] = j;
					v[j] = 1;
					break;
				} else {
					cnt--;
				}
			}
		}
	}
}

参考题目

Luogu P2524
利用康托展开将排列映射到整数。

Luogu P1379
利用康托展开存储局面，进行BFS。