【康托展开】全排列中某一排列的字典序计算问题

这也是排列组合中的一个问题，不是【搜索】的技巧，但也有一定的关系，可以简化搜索状态的复杂度。

如果，在某一个问题中，我们想知道一个排列是否出现过，由于全排列有N!个，我们一一比对，要O(N!)的复杂度。这就会拖累整体算法。

下面我们运用一种方法——康托展开，用O(N!)个bool的空间，得到O(N²)的复杂度。

一、康托展开介绍

康托展开是一个特殊的哈希函数，将全排列中的每个排列分别按字典序从小到大映射到0 ~ (N!-1)。

举例如下，计算{1, 2, 3, 4}的全排列，有24个排列：

#include <iostream>
#define Swap(x, y) {int t = x; x = y; y = t;} 
using namespace std;  

int data[] = {1, 2, 3, 4}; //4!=24 
void permutation(int begin, int end) {
	if (begin == end) {
		for (int i = 0; i <= end; ++i) 
			cout <<data[i] <<" ";
		cout <<endl;
		return;
	} 
	for (int i = begin; i <= end; ++i) {
		Swap(data[begin], data[i]);
		permutation(begin + 1, end);
		Swap(data[begin], data[i]);
	}
}  
int main() {
	permutation(0, 3); 
	return 0;	
}

计算出来的结果，按照字典序从小到大排序如下，最小的是1234，然后是1243，…

1. 1 2 3 4
2. 1 2 4 3
3. 1 3 2 4
4. 1 3 4 2
5. 1 4 2 3
6. 1 4 3 2 
7. 2 1 3 4
8. 2 1 4 3
9. 2 3 1 4
10. 2 3 4 1
11. 2 4 1 3
12. 2 4 3 1
13. 3 1 2 4
14. 3 1 4 2
15. 3 2 1 4
16. 3 2 4 1
17. 3 4 1 2
18. 3 4 2 1
19. 4 1 2 3
20. 4 1 3 2
21. 4 2 1 3
22. 4 2 3 1
23. 4 3 1 2
24. 4 3 2 1 

因此，有如下的映射，将最小的1234映射到第0个位置，最大的4321映射到第23个位置：

状态	1234	1243	1324	1342	1423	…	4312	4321
Cantor	0	1	2	3	4	…	22	23

Cantor展开的实质，就是计算这个排列位于第几小。

二、手动计算Cantor展开

如果我们要计算出每个排列，并排序，然后寻找，那就爆炸了。可以这么找：

1234：

• 首位小于1的所有排列：比1小的数没有，后面三个数有3!种排列可能，因此排列数目为0*3! = 0；
• 首位为1，第二位小于2的所有排列：排除1，小于2的数没有，后面两个数有2!种排列可能，因此排列数目为1*0*2! = 0；
• 前两位为12，第三位小于3的所有排列：排除前面的1,2，小于3的数没有，因此排列数目为1*1*0*1! = 0；
• 前三位为123，第四位小于4的所有排列：排除前的1,2,3，小于4的数没有，因此排列数目为1*1*1*0*0! = 0；
• 结论：0+0+0+0 = 0，因此1234为第0个排列。

2143：

• 首位小于2的所有排列：比2小的数有1，后面三个数有3!种排列可能，因此排列数目为1*3! = 6；
• 首位为2，第二位小于1的所有排列：排除2，小于1的数没有，后面两个数有2!种排列可能，因此排列数目为1*0*2! = 0；
• 前两位为21，第三位小于4的所有排列：排除前面的2,1，小于4的数为3，因此排列数目为1*1*1*1! = 1；
• 前三位为2143，第四位小于3的所有排列：排除前的1,2,4，小于3的数没有，因此排列数目为1*1*1*0*0! = 0；
• 结论：6+0+1+0 = 7，因此2143为第7个排列。

其他的就不举例了。

总结公式如下，某个排列a[]的字典序X（X从0开始，0 <= i < n），C(a[i])为a[i]后面小于a[i]的数的个数：
X = C(a[0]) * (n - 1)! + C(a[1]) * (n - 2)! + C(a[2]) * (n - 3)! + ... + C(a[n-1]) * 0!

三、代码模板

#include <iostream> 
using namespace std;  

int fact[] = {1, 1, 2, 6, 24, 120}; //(i!)=factory[i]; 
int cantor(int perm[], int n) {
	int ans = 0;
	for (int i = 0; i < n; ++i) { //对排列的每个数
		int count = 0; //计算排列后面小于perm[i]的数 
		for (int j = i + 1; j < n; ++j) 
			if (perm[j] < perm[i]) 
				++count;
		//小于perm[i]的数放在perm[i]上，后面有fact[n-1-i]种排列可能 
		ans += count * fact[n - 1 - i]; 
	}
	return ans;
}

int main() { 
	int perm[] = {2, 1, 4, 3}, perm1[] = {2, 4, 3, 1}, perm2[] = {4, 3, 2, 1};
	cout << cantor(perm, 4) << " ";
	cout << cantor(perm1, 4) << " ";
	cout << cantor(perm2, 4) << " ";
	return 0;	
}