简介

康托展开是一个全排列到自然数的双射，即任意一个大小为n的排列（数组）都可映射为一个唯一的整数，对应当前排列在所有由小到大的全排列中的序号。反之，我们亦可根据该序号以及排列的大小n逆推回原来的序列。

在算法竞赛中，康托展开常用来解决全排列的字典序问题以及构建哈希表时对空间、时间的优化。

康托展开

输入：大小为 \(n\) 的排列
输出：对应该排列的字典序排名（不超过 \(n!\) 的整数）
时间复杂度：

• 朴素： \(O(n^2)\)
• 树状数组优化：\(O(n*log(n))\)

1. 公式

不讲理论，直接上公式： \(rank = \sum_{i=1}^{n} [a_i \times (n-i)!] + 1\)
设排列为 \(perm\) ，这里 \(a_i\) 表示集合 \(S = \{perm[k]，k > i ∧ perm[k] < perm[i] \}\) 的元素个数（集合的模）。

例子 1：

有排列 \(perm[3] =\{3,2,1\}\) ；我们可以从上帝视角知道，该排列的大小为 \(3\) 且是排名最靠后（字典序最大）的一个排列，顺序为 \(3! = 6\) 。那么这个答案 \(6\) 如何通过康托展开求得呢。

1. 设 \(rank\) 为该排列的字典序排名，初始化 \(rank = 0\)
2. 第一位是 \(3\)，在第一位之后比 \(3\) 小的元素有 \(\{2,1\}\) 两个。不难想到，以 \(2\) 或 \(1\) 占第一位的排列其字典序一定会排在以 \(3\) 占用第一位的排列之前，总个数为 \(2 \times 2!\) 。\(rank = rank + 2 \times 2! = 4\)
3. 第二位是 \(2\)，在第二位之后比 \(2\) 还小的元素有 \(\{1\}\) 一个，因此排名在这之前的排列个数占用了 \(1 \times 1!\) 个。\(rank = rank + 1 \times 1! = 5\)
4. 第三位是 \(1\)，到这里已经是最后一位，前面的元素已经固定，最后一位也随之确定。这里， \(rank = rank + 0 \times 0! = 5\)
5. 至此我们已经算出有 \(5\) 个排列在当前排列之前，因此加上当前排列本身即可得出当前排列的排名。 \(rank = rank + 1 = 6\)

至此康托展开步骤完成。

例子 2：

再来看一个例子， \(perm[4]=\{2,4,3,1\}\)。步骤是差不多的，这里再走一遍。

1. 设 \(rank\) 为该排列的字典序排名，初始化 \(rank = 0\)
2. 第一位是 \(2\)，在第一位之后比 \(2\) 小的元素有 \(\{1\}\) 一个。因此在第一位元素为 \(2\) 的排列之前的排列总数为 \(1 \times 3!\)。\(rank = rank + 1 \times 3! = 6\)
3. 第二位是 \(4\)，在第二位之后比 \(4\) 小的元素有 \(\{3,1\}\) 两个（第一位的 \(2\) 也小于 \(4\)，但我们计算的是 \(perm\) 之前的排列数，此时 \(2\) 已经固定在了第一位，因此往后找比 \(4\) 小的数即可）。\(rank = rank + 2 \times 2! = 10\)
4. 第三位是 \(3\)，在第一位之后比 \(3\) 小的元素有 \(\{1\}\) 一个。\(rank = rank + 1 \times 1! = 11\)
5. 第三位是 \(1\)，最后一位， \(rank = rank + 0 \times 0! = 11\)
6. 至此我们已经算出有 \(10\) 个排列在当前排列之前，加上当前排列本身即可得出当前排列的排名。 \(rank = rank + 1 = 12\)

举例就到这里结束，下面是康托展开的 C++ 实现。

2. 实现

int fact[7] = {1,1,2,6,24,120,720}; //预处理阶乘，避免重复计算

int Cantor(int s[],int size) {
    int rank = 0; 
    for (int i=0;i<size;i++) {
        int a = 0; 
        for (int j=i+1;j<size;j++) { //往后统计比当前元素小的元素个数
            if (s[j] < s[i]) 
                a++;
        }
        rank += a * fact[size-i-1];//公式
    }
    return rank + 1; //加上本身，得到最终排名
}

逆康托展开

输入：排列的大小、排列的字典序排名
输出：排列数组
时间复杂度：

• 朴素： \(O(n^2)\)
• 树状数组优化：\(O(n*log(n))\)

1. 思路

在掌握康托展开的方法后，逆康托展开的思路相对好梳理。简单的说，将康托展开的步骤逆过来便可根据排列大小以及排名推出原排列。

例子 1：

在上面康托展开的例子中我们已经知道， \(perm[3]=\{3,2,1\}\) 的排名为 \(6\) 。这里演示一遍通过排名以及排列大小逆推原排列的过程。

1. 初始化，排列大小为 \(3\) ，排名为 \(6\) 。\(rank=6\)；
2. 排名减去自身，得到顺序在当前排列之前的排列数。\(rank = rank - 1 = 5\)；
3. 通过排名求排列第一位元素：
   • 令 \(a = rank \div 2! = 2\) ，得该排列有 \(2\) 个元素比第一位元素小。因此第三个没有被使用过的元素即为所求排列第一位元素的值。 \(perm[0] = 3\)
   • 第一位元素确定，过滤掉按第一位元素排名的排列（即第一位元素比 \(3\) 小的排列数），\(rank = rank \% 2! = 1\)（相当于 \(rank = rank - 2 \times 2!\) ）
     
4. 通过排名求排列第二位元素：
   • 令 \(a = rank \div 1! = 1\) ，得该排列有 \(1\) 个元素比第二位元素小。找出第二个没有被使用过的元素。\(perm[1]=2\)
   • 第二位元素确定，过滤掉按第二位元素排名的排列，\(rank = rank \% 1! = 0\)
5. 到这里，前两位元素已经确定，最后一位便是待定元素集中唯一没有被使用过的元素。当然，我们也可以按流程走，通过排名求排列第三位元素：
   • 令 \(a = rank \div 0! = 0\) ，得该排列有 \(0\) 个元素比第三位元素小。找出第一个没有被使用过的元素。\(perm[2]=1\)

至此我们已经通过排名和排列大小得到了对应的排列

例子 2：

\(perm[4]=\{2,4,3,1\}\)，排名为 \(12\)

1. 初始化，排列大小为 \(4\) ，排名为 \(12\) 。\(rank=12\)；
2. 排名减去自身，得到顺序在当前排列之前的排列数。\(rank = rank - 1 = 11\)；
3. 通过排名求排列第一位元素：
   • 令 \(a = rank \div 3! = 1\) ，得该排列有 \(1\) 个元素比第一位元素小。找出第二个没有被使用过的元素。 \(perm[0] = 2\)
   • \(rank = rank \% 3! = 5\)
4. 通过排名求排列第二位元素：
   • 令 \(a = rank \div 2! = 2\) ，得该排列有 \(2\) 个元素比第二位元素小。找出第三个没有被使用过的元素。\(perm[1]=4\)
   • \(rank = rank \% 2! = 1\)
5. 通过排名求排列第三位元素：
   • 令 \(a = rank \div 1! = 1\) ，得该排列有 \(1\) 个元素比第三位元素小。找出第二个没有被使用过的元素。\(perm[2]=3\)
   • \(rank = rank \% 1! = 0\)
6. 通过排名求排列第四位元素：
   • 令 \(a = rank \div 0! = 0\) ，得该排列有 \(0\) 个元素比第四位元素小。找出第一个没有被使用过的元素。\(perm[3]=1\)

与我们从上帝视角得到的答案一致，下面讲一讲逆康托展开的 C++ 实现

2. 实现

int fact[7] = {1,1,2,6,24,120,720}; //预处理阶乘，避免重复计算

int* revCantor(int size,int rank) {
    rank--; //排名减去自身
    bool vis[size+1]; //标记未使用过的元素
    int *perm = (int*)malloc(sizeof(int)*size);
    memset(vis,false,sizeof(vis));
    memset(perm,-1,sizeof(perm));
    
    for (int i=0;i<size;i++) {
        int a = rank / fact[size-i-1]; //有多少个未使用的元素比当前位置的元素小
        rank %= fact[size-i-1]; //a已求得，更新rank，过滤掉按当前位置排名的排列
        for (int j=1;j<=size;j++) { //找出第 a+1 个未使用过的元素
            if (!vis[j] && !(a--)) {
                vis[j] = true;
                perm[i] = j;
                break;
            }
        }
    }
    
    return perm;
}

学习笔记-康托展开与逆康托展开

原文：https://www.cnblogs.com/doublebit/p/12254804.html