康托展开求全排列

缘起

【1】中，我们展示了求全排列的一种dfs方法. 其实求全排列还有一种通过哈希进行的妙法. 就是康托展开. 所以来学习学习~

分析

给出n, 然后1~n组成全排列. 学过排列组合知识的人都知道有 n! 种不同的全排列. 然后【1】中通过dfs给出了按字典序升序的1~n的全部全排列.

那么我们需要n!大小的int数组来哈希全部全排列. 排在第一的，即a[1]就是1,2,3….,n 这个字典序最小的全排列, 而a[n!]就是最后那个字典序最大的全排列 n,…,2,1

而康托展开解决的问题是如何求出a[i]对应的全排列（有网上说这叫逆康托展开）, 以及给出一个全排列, 求出该全排列排在a的第几(康托展开), 即求i使得a[i]等于这个全排列.

康托展开是一种基于哈希的压缩状态的妙法. 即可以将一个全排列（一种状态）用一个正整数简明扼要的表达. 这对于解题是非常有用的. 就好像之前做过的 二进制压缩 一样. 这个在【2】中会用到. 即著名的八数码问题.

康托展开

即给你一个全排列. 例如 n=5, 以及 3 4 1 5 2 这个全排列（下简称P）. 问你这个全排列在所有全排列中排第几. 也就是问一个i, 上面的a[i]表示该全排列.

其实就是排列组合. 3前面有1,2两个数字. 所以P之前有2*(5-1)!个全排列. 然后3固定（即全排列首位固定）.全排列第二位可以选择1 2（注意, 因为3已经被选掉了）, 所以P前面还有 2*(5-2)!个全排列. 然后3和4固定. P前面有

0*(5-3)!个全排列. 然后3、4、1固定. P前面有1*(5-4)!个全排列(因为5之前1、3、4都被选掉了,唯余2)，然后3、4、1、5固定. P前面有0*(5-5)!个全排列. 所以3、4、1、5、2这个全排列在所有全排列中按字典序升序排

1
2*(5-1)!+2*(5-2)!+0*(5-3)!+1*(5-4)!+0*(5-5)!

个全排列. 所以我们不难总结出公式

给定1~n的全排列 p[1,…,n], 它排在第（加1是因为求和式子计算出来的仅仅是排在它前面的）

$$
1+\Sigma_{1\le i \le n}x[i](n-i)! = 1+\Sigma_{0\le i \le n-1}x[n-i]i!
$$

其中x[i](1<=i<=n) 是 [1,p[i]) 中尚没有被固定下来的数字的个数. 之所以要对上式左边进行变形, 是因为 i! 可以迭代求解方便.

c++实现康托展开如下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include "stdafx.h"

#include <stdio.h>
#define LOCAL

int n, p[15],x[15]; // 不超过10的全排列
bool v[15];

int count(int i) // [1,p[i])内v为false的个数
{
	int ans = 0;
	for (int j = 1; j<p[i]; j++)
	{
		if (!v[j])
		{
			ans++;
		}
	}
	v[p[i]] = true; // 它也要固定下来
	return ans;
}

int cantor()
{
	int ans = 0;
	for (int i = 1; i<=n; i++)
	{
		x[i] = count(i);
	}
	for (int i = 0, fac = 1; i<n; i++)
	{
		ans+=x[n-i]*fac;
		fac*=(i+1);
	}
	return ++ans; // 因为ans计算的只是排在之前的全排列个数
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1; i<=n;i++)
	{
		scanf("%d", p+i);
	}
	printf("%d\n", cantor());
	return 0;
}
/*
测试数据
3
3 2 1
*/

逆康托展开

给定一个全排列要你计算它的排名是正向问题，没有太大意义. 实际题目中可能更多的是给你排名要你计算位于此排名的全排列是什么. 只有实现了这个，压缩状态才有意义.

逆康托展开问题就是给你一个正整数（在 [1,n!] 中）a，

$$
a=1+\Sigma_{0\le i \le n-1}x[n-i]*i!
$$

则其实就是给你一个 a 在[0, n!)内, 且

$$
a=\Sigma_{0\le i \le n-1}x[n-i]*i!
$$

a除以(n-1)! 因为a<n!, 所以商<n, 而注意到
$$
\begin{align}
\frac{a}{(n-1)!} &=\frac{\Sigma_{0\le i \le n-1}x[n-i]i!}{(n-1)!} \
&= x[1]+\frac{\Sigma_{0\le i \le n-2}x[n-i]i!}{(n-1)!}
\end{align}
$$
而
$$
\Sigma_{0\le i \le n-2}x[n-i]i!\le \Sigma_{0\le i \le n-2}ii!
$$
因为你完全逆序的话, 即n,n-1,…,1 才能达到上式的右边.而i=i+1-1, 用裂项相消法不难知道

$$
\Sigma_{0\le i \le n-2}x[n-i]*i!<(n-1)!
$$

所以a除以(n-1)! 得到的商就是x[1]. 余数<(n-1)!, 所以使用余数再除以(n-2)!, 商就是x[2]. 如此往复（类比于辗转相除法）, 最后除以(n-n)!,商就是x[n]. 而得到了x[1,…,n] 对于求出原全排列有什么作用呢?

首先x[1]+1就是p[1]. 而x[2]是[1,p[2]) 范围内尚未被固定的数的个数. 则p[2]应该是x[2]+1, 但是不能这么简单. 因为[1,p[2]] 之间的数可能被占用掉了. 所以要加上. 就是下面代码32行做的事情.

逆康托展开的c++实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include "stdafx.h"

#include <stdio.h>
#define LOCAL

int n, p[15],x[15], a; // 求1~n的按字典序升序第a位的全排列
bool v[15];

int fac() // 计算 n!
{
	int ans =1;
	for (int i = 1; i<=n; i++)
	{
		ans*=i;
	}
	return ans;
}

void rcantor() // 逆康托展开
{
	a--;
	int f = fac();
	for (int i = n;i; i--)
	{
		f/=i;
		x[n-i+1] = a/f;
		a%=f;
	} // 得到 x[1,...,n],下面利用x求出p
	for (int i = 1; i<=n; i++)
	{
		p[i] = x[i]+1; // 初始设定p[i]
		for (int j = 1; j<=p[i]; j++) // 看看[1,p[i]]有没有被占坑的
		{
			if (v[j]) // 如果被占坑了, 则少算了一个
			{
				p[i]++;
			}
		} // 改变 p[i]
		v[p[i]] = true; // 把坑占上
	}
	for (int i = 1; i<=n; i++)
	{
		printf("%d ", p[i]);
	}
	puts("");
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &a);
	rcantor();
	return 0;
}
/*
测试数据
3 4
*/

ps:逆康托展开求全排列其实实现了 c++ stl 中的 next_permutation 和 prev_permutation.

参考

【1】https://yfsyfs.github.io/2019/05/27/全排列/

【2】https://yfsyfs.github.io/2019/09/13/hdu-1043-Eight-%E5%85%AB%E6%95%B0%E7%A0%81-%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80-%E6%90%9C%E7%B4%A2/