算法基础与在线实践,计算机算法基础知识

http://www.Sina.com/http://www.Sina.com /

本文记录了康托展开和反联谊展开的原理及其应用。

康托展开与逆康托展开

例如，对于1至4的所有阵列[ 1，2，3，4 ]和[ 4，3，2，1 ]，已知在字典顺序中前者是该所有阵列集合的第一个，而后者是该集合的最后一个。 那么，纸箱展开是给定n n n个n位数的所有排列，根据纸箱展开式可以决定应该是词典顺序中第“第几个”的所有排列。

色调展开是计算某个全部排列模式在其全部排列集合中的词典顺序，或者排名，由于其映射关系是唯一且单调的，所以该映射关系是可逆的。 也就是说，我们给定了所有数组的所有字符和某个词典编号，我们就可以利用逆纸箱展开得到对应的所有数组。

序言：

给出全数组，计算其词典顺序。 直观上，以[ 2，3，4，1 ]为例说明铁路超高展开的动作步骤。

求出辞典顺序为rank=0rank=0rank=0rank=0

假设第1位是2，以1开始的所有数组都一定排在这个所有数组的前面，则以1开始的所有数组为(3)！ () 6种，rank=rank13！=6 rank=rank 1*3！=6 rank=rank 13！=6。 2位是3，以1和2为2位的所有排列都必须在这个圈排列的前面。 但是，我们已经把2排在了前头，所以没有必要考虑2是第二位的情况，只需要计算1是第二位的情况。 r a n k=r a n k 1 2！=8 rank=rank 1 * 2！=8 rank=rank 12！=8。 第三位是4，同时用1计算第三位的所有情况。 r a n k=r a n k 1 1

! = 9 rank = rank + 1 * 1! = 9 rank=rank+1∗1!=9。最后一位，是不需要判定的，因为前 n − 1 n - 1 n−1 位给定后，第 n n n 位自定。当然，为了也适应前面推导，可以记 r a n k = r a n k + 0 ∗ 0 ! = 9 rank = rank + 0 * 0! = 9 rank=rank+0∗0!=9。

由是，排在 [2, 3, 4, 1] 之前的全排列共有 9 个，那么 [2, 3, 4, 1] 应当是第 10 个全排列。总结康托展开公式为：
r a n k = a n ( n − 1 ) ! + a n − 1 ( n − 2 ) ! + ⋯ + a 1 0 ! red{rank = a_n(n - 1)! + a_{n-1}(n - 2)! + cdots + a_10!} rank=an​(n−1)!+an−1​(n−2)!+⋯+a1​0!
其中， a i a_i ai​表示原排列中，排在下标 i i i 后面的，比下标 i i i 的字符还小的字符个数。当然，如果排名是从 1 开始的话，最终结果应当再 + 1。

C++ 实现 //对前 10 个自然数(0 ~ 9)的阶乘存入表//以免去对其额外的计算const int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};/** * @brief 康拓展开 * * @param[in] permutation 输入的一个全排列 * @param[out] num 输入的康拓映射，即是第几个全排列 */int contor(const vector<int>& permutation) { int num = 0; int len = permutation.size(); for (int i = 0; i < len; ++i) { int cnt = 0; // 在 i 之后，比 i 还小的有几个 for (int j = i + 1; j < len; ++j) if (permutation[i] > permutation[j]) ++cnt; num += cnt * fact[len - i - 1]; } return num + 1;}

2.逆康托展开
同样以[2, 3, 4, 1]为例，以说明逆康拓展开的执行方法。这里输入和输出互反，同时，我们还需要输入全排列的字符个数(否则有无穷多个解)。
给定，字符个数 4，字典序序号 10，首先字典序 - 1 得到排在该字典序前的全排列个数，然后：

9 / 3! 结果，商 1 余 3，说明首位要余出一个给 当前没用过的，最小的一个字符，因为它们占据了前 6 个排序。这里 “1” 没有用过，又是最小的字符，因此，我们应当使用 “2” 作为首位，并标记其已经使用。取余数进行下一步操作。3 / 2! 结果，商 1 余 1，说明第二位要余出一个给 当前没用过的，最小的字符。这里 “1” 没有用过，“2” 已经用了。因此，我们应当使用 “3” 作第二位。1 / 1! 结果，商 1 余 0，说明第三位要余出一个给 当前没用过的，最小的字符。这里 “1” 没有用过，“2” 已经用了，“3”也用了。因此，我们应当使用 “4” 作第三位。同康托展开，最后一位无需判断，所有字符中至今未使用的填入即可。 C++ 实现 //对前 10 个自然数(0 ~ 9)的阶乘存入表//以免去对其额外的计算const int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};/** * @brief 逆康拓展开 * * @param[in] bits 给定全排列的使用数字个数 * @param[in] num 给定全排列的次位 * @param[out] permutation 输出对应的全排列 */vector<int> revContor(int bits, int num) { num = num - 1; //有 num - 1 个排列比目标序列要小 vector<bool> vis(bits + 1, false); vector<int> permutation(bits, -1); int n, residue = num; for (int i = 0; i < bits; ++i) { n = residue / (fact[bits - i - 1]); residue = residue % (fact[bits - i - 1]); for (int j = 1; j <= bits; ++j) { if (!vis[j] && !(n--)) { vis[j] = true; permutation[i] = j; break; } } } return permutation;}

4. 应用
康托展开与逆康托展开与全排列的联系十分密切，在解决全排列的字典序问题时能够发挥极大的作用。
此外，康托展开也是一个数组到一个数的映射，可以应用于hash中进行空间压缩。例如，在八数码问题中，我们可以把一种排列状态压缩成一个整数存放在数组中。