康托展开及其应用

51 阅读 0 评论 34 点赞

我是靠谱客的博主高贵麦片，最近开发中收集的这篇文章主要介绍康托展开及其应用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

康托展开是一种特殊的哈希函数，用阶乘的线性组合来表示一个数x，即x = a[n] * n! + a[n-1] * (n-1)! + .... + a[1] * 1! , 其中0 <= a[i] <= i, i = 1,2...,n.例如19 = 3 * 3! + 0 * 2! + 1 * 1! , 所以可以用 [3, 0, 1] 来表示19。（网上有很多博客把康托展开定义为 X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!，但本人认为x = a[n] * n! + a[n-1] * (n-1)! + .... + a[1] * 1!更容易理解。）

康托展开和其逆展开常用于全排列问题。在给定的n个不同的数的全排列中，一共有n!中不同的组合，即有n !个不同的数. 我们可能会被问及：（1）对一个数x，它在这n! 个数中排在第几位？（2）在这n！个数中，第K小的数是什么？可能你会觉得很简单，把所有的排列从小到大列举出来就行了。当n比较小时，这个方法是可行的，但n稍微增大时，复杂度急剧增大，所以穷举不是好办法。

一、首先解决第一个问题：对一个数x，它在全排列中排在第几位。

设a=a[n-1] a[n-2] a[n-3] ... a[0], 其中a[n-1] != a[n-2] != .... != a[1] != a[0]. 令函数 L(a[i]) 表示a[i-1] 、a[i-2]、... 、a[0]中小于a[i]的个数，则a= a[n-1] a[n-2] ... a[0] 在这n!个数的的大小位置为:P(a) = L(a[n-1]) * (n-1)! + L(a[n-2]) * (n-2)! + .... + L(a[1]) * 1!.

例如1，2，3的全排列，下面分别计算每中情况的排序位置.

(1) 123: L(1) * 2! + L(2) * 1! = 0 * 2! + 0 * 1! = 0; 因为a[1] = 2和a[0] = 3都比a[2] = 1大, 所以L(a[2]) = L(1) = 0; 同理L(a[1]) = L(2) = 0;

即P(123) = 0;

(2) 132 :L(1) * 2! + L(3) * 1! =0 * 2! + 1 * 1! = 1, 即P(132) = 1;

(3) 213 :L(2) * 2! + L(1) * 1! =1 * 2! + 0 * 1! = 2, 即P(213) = 2;

(4) 231 :L(2) * 2! + L(3) * 1! =1 * 2! + 1 * 1! = 3, 即P(231) = 3;

(5) 312 :L(3) * 2! + L(1) * 1! =2 * 2! + 0 * 1! = 4, 即P(312) = 4;

(6) 321 :L(1) * 2! + L(3) * 1! =2 * 2! + 1 * 1! = 1, 即P(321) = 5;

好了，各位不妨考虑一下:在1、2、3、4，5的全排列中，34512排在第几位？

答案是：P(34512) = 2 * 4! + 2 * 3! + 2 * 2! + 0 * 1! .

二、在这n个数的全排列中，第K小的数是什么？

这里需要注意，我们定义的排序是从0开始算前的，即我们称123是1、2、3全排列第0小的数。

对于这个问题，我们的方法与第一部分恰好相反：（1）先对K进行康托展开， (2)根据康托展开的结果组合数字。这样说有些抽象，下面与一个例子进行说明？

问题：对于1、2、3、4的全排列，第19小的数字a[3]a[2]a[1]a[0]是什么？

因为 19 = 3 * 3! + 0 * 2! + 1 * 1! = [3, 0, 1];

其实上面的等式就是 L(a[3]) * 3! + L(a[2]) * 2! + L(a[1]) * 1!, 所以L(a[3]) = 3, L(a[2]) = 0, L(a[1]) = 1,说明a[3] 比其后的3个数都大，所以a[3] = 4,同理的a[2] = 1, a[1] = 3,所以a[0]=2, 即第19小的数为 4132。

三、一个具体的解题应用

Sicily1151魔板点击打开链接是一道比较简单的广搜题，它的难点在于如何标记状态。从题目中我们可知一共有8!种状态，如果我们开一个8维的矩阵Visited[8][8][8][8][8][8][8][8],那显然没有这么大的内存。在这里我们注意到每种状态x都是1、2、3、4、5、6、7、8的全排列的其中一种情况，所以这里可以做一个哈希映射，求出x在全排列中所处的位置，这样我们就只需要开一个8! 的一维数组。

其实这道题还可以直接使用一个关联容器map<string, bool>visited来处理，对每种状态x，当正在访问x时，令visited[x.toSting()] = true 即可标记。