康托展开与逆康托展开（基础）

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。（摘自百度百科）

此为康托展开的公式
在csdn看到一篇博文很好
给出链接：添加链接描述
1.概述
举例而言，对于 1 ~ 4 的一个全排列 [1, 2, 3, 4] 和 [4, 3, 2, 1]，我们知道，从字典序而言，前者是该全排列集的第一个，后者是该集的最后一个。那么，所谓康托展开，即给定一个 n nn 位数的全排列，我们可以根据康托展开公式确定其应当是字典序中的第“几”个全排列。
由于康托展开计算的是某个全排列方式在该全排列集合中的字典序(或者说是排名)，其映射关系唯一且单调，故该映射关系是可逆的。即，我们给定一个全排列的所有字符，以及某个字典序号，我们可以利用逆康托展开得到相应的那个全排列
上代码
康托展开

//对前 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;
}

逆康托展开

```cpp
//对前 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;
}