简述

康托展开可以求出一个全排列在所有全排列中的字典序

也可以逆操作，通过元素个数和字典序，求出第 xx 个全排序状态

例如，对于 {1,2,3} 3 个数的全排列，共有 3!=63!=6 种状态

1
2
3
4
5
6
0: 1 2 3
1: 1 3 2
2: 2 1 3
3: 2 3 1
4: 3 1 2
5: 3 2 1

使用康托展开可以通过 2 3 1 求得值 3 ，逆康托展开可以通过值 4 来求得 3 1 2

核心算法

X=A1⋅(n−1)!+A2⋅(n−2)!+…+An⋅0!X = A_{1}\cdot(n-1)! + A_{2}\cdot(n-2)! + \ldots + A_{n}\cdot0!

  • XX ：康托展开值，指此排列前面还有多少种排列
  • nn ：总共有多少数字
  • aia_{i} ：第 ii 位上的数字
  • AiA_{i} ：在第 ii 位后面的数中，比 aia_{i} 小的数的个数

这个式子鄙人为了理解方便，稍微改动了一下

举例

康托展开

例一

求 2143 是 {1,2,3,4} 的全排列中第几大的数

  • 第一位是 2 ，后面比 2 小的有 1 个数，故写成 1×3!1\times3!
  • 第二位是 1 ，后面没有比 1 小的数，故写成 0×2!0\times2!
  • 第三位是 4 ，后面比 4 小的有 1 个数，故写成 1×1!1\times1!
  • 第四位是 3 ，后面没有数了，故写成 0×0!0\times0!

计算：1×3!+0×2!+1×1!+0×0!=71\times3!+0\times2!+1\times1!+0\times0! = 7

因为自然数是从 1 开始数的，所以 2143 是第 7+1=87+1=8 大的排列

例二

在 {1,2,3,4,5} 5个数的排列组合中，计算 34152 的康托展开值

  • 第一位是 3 ，后面有 1、2 两个， 2×4!2\times4!
  • 第二位是 4 ，后面有 1、2 两个， 2×3!2\times3!
  • 第三位是 1 ，后面没有比 1 小的， 0×2!0\times2!
  • 第四位是 5 ，后面只有一个 2， 1×1!1\times1!
  • 最后一位，老样子是 0×0!0\times0!

计算：2×4!+2×3!+0×2!+1×1!+0×0!=612\times4!+2\times3!+0\times2!+1\times1!+0\times0!=61

逆康托展开

用上面那个例子，来逆运算一遍

在 {1,2,3,4,5} 5个数的排列组合中，计算 61 对应的排列状态

  • 614!=2……13\dfrac{61}{4!}=2\ldots\ldots13 ，说明比第一位小的有两个数，故第一位为 3
  • 133!=2……1\dfrac{13}{3!}=2\ldots\ldots1 ，说明现在（3 已经被选走了）比第二位小的有两个数，故第二位为 4
  • 12!=0……1\dfrac{1}{2!}=0\ldots\ldots1 ，说明现在没有比第三位小的数，故第三位为 1
  • 11!=1……0\dfrac{1}{1!}=1\ldots\ldots0 ，说明现在比第四位小的只有一个，故第四位为 5
  • 最后剩下一个 2，肯定就是最后一位

故排列状态为 34152

代码实现

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
#include <bits/stdc++.h>
using namespace std;
const int FACT[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
int Cantor(int a[], int n)
{
    int x = 0;
    for (int i = 0; i < n; i++)
    {
        int count = 0;
        for (int j = i + 1; j < n; j++)
        {
            if (a[i] > a[j])
                count++;
        }
        x += FACT[n - i - 1] * count;
    }
    return x;
}
int *InverseCantor(int x, int n)
{
    int *a = new int[n];
    vector<int> v; // 存放当前可选数
    for (int i = 1; i <= n; i++)
        v.push_back(i);
    for (int i = n - 1; i >= 0; i--)
    {
        int r = x % FACT[i];
        int t = x / FACT[i];
        x = r;
        a[n - i - 1] = v[t];
        v.erase(v.begin() + t); // 移除选做当前位的数
    }
    return a;
}

int main()
{
    int a[] = {3, 4, 1, 5, 2};
    cout << Cantor(a, 5) << endl;
    int *b = InverseCantor(7, 4);
    for (int i = 0; i < 4; i++)
        cout << b[i] << " ";
}

为什么是这样？

康托展开本质是不断枚举在此排列之前的所有排列

例如例二，34152

从第一位看起，若要构造比当前小的，可以从后面的数字中选比 3 小的数字来放在第一位，有 1xxxx 和 2xxxx 两种可能，而后面四个位置是随意地全排列，自然是 2×4!2\times4!

在第一位已经固定为 3 的情况下看第二位，要比 4 小，可以是 31xxx 和 32xxx ，这里共有 2×3!2\times3! 种排列

以此类推，第三位已经是最小了，不能变了

然后第四位，可以把 2 换过来，变成 3412x ，而 x 只可能是 5 ，共有 1×1!1\times1! 种

最后一位已经固定了，变不了了