【算法】正逆康托展开基础

2020年03月23日旧站迁移约6.1k字预计需要22 分钟

康托展开和逆康托展开是全排列和他的字典序序号相互转化的两种算法。在有关排列方案的问题中可以作为枚举的哈希函数，在允许枚举的数据范围内具有优良的复杂度。但是一般允许枚举的数据范围大概是20以内，因为21！爆int64，所以这也是种图一乐算法。

算法作用

在$O(n^2)$复杂度中得到一个序列在他的全排列中的字典序序号。逆展开则是由一个全排列中的字典序序号快速得到序列。由树状数组优化后复杂度可以达到$O(n\log n)$

实现思路

康托展开

对于一个长度为$n$的序列，若他的第$i$位是当前可用数字集合中的第$j$小的数，则说明他经过这一位比这一位的最小可能字典序大了$j\cdot i!$。从左到右依次计算并更新可用数字的集合即可。

例如，对于${1, 2, 3}$的全排列，有表格：

排列	序号	展开	每位的可用数集
1, 2, 3	1	0 * 2! + 0 * 1! + 0 * 0!	123, 23, 3
1, 3, 2	2	0 * 2! + 1 * 1! + 0 * 0!	123, 23, 2
2, 1, 3	3	1 * 2! + 0 * 1! + 0 * 0!	123, 13, 3
2, 3, 1	4	1 * 2! + 1 * 1! + 0 * 0!	123, 13, 1
3, 1, 2	5	2 * 2! + 0 * 1! + 0 * 0!	123, 12, 2
3, 2, 1	6	2 * 2! + 1 * 1! + 0 * 0!	123, 12, 1

逆康托展开

上述过程的逆运算即可。每次算出当前位是可用数集的第几位，获取并更新可用数集即可。

具体实现

一种可能的实现方法：

const int FACT[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 静态化阶乘值
// 正康托展开
long long cantor(const vector<int> &a)
{
    long long res (0);
    int len (a.size());
    for (int i = 0; i < len; i++)
    {
        int num = 0;
        for (int j = i + 1; j < len; j++)
        {
            if (a[j] < a[i]) num++;
        }
        res += FACT[len - i - 1] * num;
    }
    return res;
}
// 逆康托展开
// \param x 字典序序号
// \param n 排列长度
vector<int> decantor(int x, int n)
{
    vector<int> vis, res;
    for (int i = 0; i <= n; i++) vis.emplace_back(i + 1);
    for (int i = n - 1; i >= 0; i--)
    {
        int now = x / FACT[i];
        x %= FACT[i];

        res.emplace_back(vis[now]);
        vis.erase(vis.begin() + now);
    }
    return res;
}

最后

以上就是康托展开的基础内容了。

这种图一乐算法既能图一乐，还篇幅短小。真的很适合水博客（草）。

文章分类

一言

最新文章

文章归档