康托展开和逆康托展开

康托展开

康托展开可以用来求一个 1∼n1\sim n 的任意排列的排名

康托展开是一个全排列到一个自然数的双射,其实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的

以下称第 xx 个全排列都是指由小到大的顺序。

在哈希表建表和全排列状态压缩的时候，康托展开则是很好使的一个方法

公式

X=an(n−1)!+an−1(n−2)!+⋯+a1⋅0!X=a_{n}(n-1) !+a_{n-1}(n-2) !+\cdots+a_{1} \cdot 0!

其中, aia_{i} 为整数,并且 0≤ai<i,1≤i≤n0 \leq a_{i}<i, 1 \leq i \leq n

显然，nn 位 (0∼n−1)(0\sim n-1) 全排列后，其康托展开唯一且最大约为 n!n!，因此可以由更小的空间来储存这些排列。由公式可将 XX 逆推出唯一的一个排列。

例题

X 星系的某次考古活动发现了史前智能痕迹

这是一些用来计数的符号，经过分析它的计数规律如下：

为了表示方便，我们把这些奇怪的符号用a~q代替

  • abcdefghijklmnopq 表示 00

  • abcdefghijklmnoqp 表示 11

  • abcdefghijklmnpoq 表示 22

  • abcdefghijklmnpqo 表示 33

  • abcdefghijklmnqop 表示 44

  • abcdefghijklmnqpo 表示 55

  • abcdefghijklmonpq 表示 66

  • abcdefghijklmonqp 表示 77

…

在一处石头上刻的符号是：

bckfqlajhemgiodnp

请你计算出它表示的数字是多少？

请提交该整数，不要填写任何多余的内容，比如说明或注释。

题解

这个题乍一看是个找规律的题目，但是实际上是一个状态压缩的套壳题,其本质是康托展开的计算题目

首先我们根据康托展开的计算公式

X=an(n−1)!+an−1(n−2)!+⋯+a1⋅0!X=a_{n}(n-1) !+a_{n-1}(n-2) !+\cdots+a_{1} \cdot 0!

可得我们需要计算阶乘的值,对于阶乘的计算,我们可以定义一个常量数组，在其中存放 0∼100\sim 10 的阶乘数据（在大量复用时节约计算时间）

1
const int factorial[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};

那么例题里的 17 个字母显然超过了 10!10!，那么对后面的数字继续进行运算即可

1
2
3
4
5
6
7
8
9
long long fact(int x)
{
    if (x <= 10)
        return factorial[x];
    long long sum = 3628800;
    for (int i = 11; i <= x; i++)
        sum *= i;
    return sum;
}

这里我们继续使用 10 的阶乘结果往上面累计乘。可以加速计算，该函数返回一个超长整型的值，即为 x 的阶乘。

当然也可以把 1-17 的阶乘都存进去

接下来就是康托展开的主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long Cantor_expansion(vector<int> sum)
{
    long long num = 0;
    int len = sum.size();//求迭代器大小，也就是统计共有多少位
    for (int i = 0; i < len; ++i)
    {
        long long ans = 0;
        for (int j = i + 1; j < len; ++j)
            if (sum[i] > sum[j])//迭代器用起来跟数组一样一样的
                ans++;
        num += ans * fact(len - i - 1);
    }
    return num;
}

我在主函数内使用向量(Vector)进行存储数据。实际使用的时候也可以使用数组进行保存数据，此处使用迭代器是因为为了兼容不同长度的康托展开压缩

本函数同样是超长整型的返回值，返回值即为康托展开压缩过后的数据。

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
#include <bits/stdc++.h>
using namespace std;
const int factorial[11] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
long long fact(int x)
{
    if (x <= 10)
        return factorial[x];
    long long sum = 3628800;
    for (int i = 11; i <= x; i++)
        sum *= i;
    return sum;
}
long long Cantor_expansion(vector<int> sum)
{
    long long num = 0;
    int len = sum.size();
    for (int i = 0; i < len; ++i)
    {
        long long ans = 0;
        for (int j = i + 1; j < len; ++j)
            if (sum[i] > sum[j])
                ans++;
        num += ans * fact(len - i - 1);
    }
    return num;
}
int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    vector<int> alpha;
    string temp;
    cin >> temp;
    int flag = 0;
    while (flag != temp.size())
        alpha.push_back(temp[flag++]);
    printf("[%lld]", Cantor_expansion(alpha));
    return 0;
}

逆康托展开

对于全排列序列与字典数来说，康托展开是一个双射，既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出 nn 的全排列中第 xx 大排列

举个例子吧：

对于 1,2,3,4,5 五个数字组成的数列,求字典序为 10 的数列

首先用 10−110-1 得到 99，说明 xx 之前有 99 个排列.(将此数本身减去 11 )

第一个数：9/(5−1)!=0…99/(5-1)! =0\dots 9 ,所以第一个数是当前未出现的第 0 个数：11

第二个数：9/(4−1)!=1…39/(4-1)! =1\dots 3 ,所以第二个数是当前未出现的第 1 个数：33

第三个数：3/(3−1)!=1…13/(3-1)! =1\dots 1 ,所以第二个数是当前未出现的第 1 个数：44

第四个数：1/(2−1)!=1…01/(2-1)! =1\dots 0 ,所以第二个数是当前未出现的第 1 个数：55

第五个数：0/(1−1)!=0…00/(1-1)! =0\dots 0 ,所以第二个数是当前未出现的第 0 个数：22

就这样，字典序为 1010 的全排列就是 1,3,4,5,2

例题

使用上文的例题,将压缩后的数重新展开回字符串

输入格式：第一行是全排列元素个数，第二行是待展开的字典序

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 factorial[11] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
long long fact(int x)
{
    if (x <= 10)
        return factorial[x];
    long long sum = 3628800;
    for (int i = 11; i <= x; i++)
        sum *= i;
    return sum;
}
vector<int> De_Cantor_expansion(int bits, long long num)
{
    vector<bool> vis(bits + 1, 0);
    vector<int> arr(bits, -1);
    long long n, temp = num;
    for (int i = 0; i < bits; ++i)
    {
        n = temp / fact(bits - i - 1);
        temp = temp % fact(bits - i - 1);
        for (int j = 1; j <= bits; ++j)
            if (!vis[j] && !(n--))
            {
                vis[j] = 1;
                arr[i] = j;
                break;
            }
    }
    return arr;
}
int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    long long n, sum;
    cin >> n >> sum;
    vector<int> ans;
    ans = De_Cantor_expansion(n, sum);
    for (auto ch : ans)
        cout << (char)(ch + 96);
    return 0;
}