康托展开、逆康托展开

一、什么康托展开和逆康托展开？

康托展开是一个全排列到自然数的双射。什么意思呢？就是把1~n的所有排列按字典序排序，这个排列的位次就是它的排名。康托展开是通过某个排列可以算出该排列的位次，反之，通过字典序的位次也能算出该排列，这个就是逆康托展开。康托展开常用于构建哈希表时的空间压缩。

二、康托展开示例

假设有个数组[1,2,3,4,5]的其中某个排列为[3,5,2,1,4]。

• 对于排列中的每一个数，计算它在当前排列中比它小的数的个数。
• 用这个数乘以剩余可用位置数的阶乘。
• 将这些乘积相加。

1.首先看第一个数 3，不管第一位是什么数，后面都有四位数，那么这四位数全排列的方式有 4！种，而如果第一位是 1 或 2 都会比3开头的字典序要小，所以可以令1，2分别作为开头，这样的话就会有 2 * 4！种排法要比 [3,5,2,1,4]这种排法的字典序要小。

那么第一个数是1，2时候的字典序的个数数完了是 2 * 4！种，且这些字典序都要比 [3,5,2,1,4]的字典序要小。

还有其他的排列方式比 [3,5,2,1,4]的字典序要小的吗？

2、现在找下一位数5，这时3已经用过了，所以从剩下的 1，2，4 里挑选比5小的数，一共3个，后面还剩三位，也就是3！种排列方式，那么这时候比  [3,5,2,1,4] 字典序要小的又有  3 * 3！种。

3、再看第三位数2，这时3，5都用了，所以从剩下的 1，4三个数中找比4小的数的个数，有1个比4小，所以这时候也可以有 1 * 2! 种排列方式的字典序小于 [3,5,2,1,4]

4、再看第四位数1，这时候会有 0 * 1！种

5、再看第五位数4，这时1，2，3，5已经用过了，这时候会有0 * 0！种

按照这样统计下去，答案就是2*4！+3*3！+1*2！+0*1！+0*0！= 48 +18 +2 +0 +0 = 68

注意我们统计的是比[3,5,2,1,4]小的排列,所以最后 [3,5,2,1,4] 的排序号为 68+1 = 69

康托展开c++代码

#include <iostream>
#include <vector>

using namespace std;

// 计算阶乘
int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; ++i)
        result *= i;
    return result;
}

// 康托展开：将排列映射到一个字典序中的整数
int cantorExpansion(vector<int>& perm) {
    int n = perm.size();
    int result = 0;
    vector<bool> used(n + 1, false); // 标记数字是否已被使用

    for (int i = 0; i < n; ++i) {
        int smaller_count = 0;
        
        // 统计当前数字右边比它小的数字个数
        for (int j = 1; j < perm[i]; ++j) {
            if (!used[j]) smaller_count++;
        }

        // 计算当前位置的贡献
        result += smaller_count * factorial(n - i - 1);
        used[perm[i]] = true;  // 标记该数字为已使用
    }

    return result + 1;  // 由于序列是从1开始，所以需要+1
}

int main() {
    vector<int> perm = {3, 1, 2};  // 示例排列
    cout << "康托展开结果: " << cantorExpansion(perm) << endl;
    return 0;
}

三、逆康托展开示例

假设康托展开值为68(排名序号要减去1)，排列的长度是5，我们希望找到原始排列。

• 减去每一位对应的阶乘，找到每一位对应的数字。
• 将这些数字按照顺序填入排列中。

需要用到的阶层 4！= 24 ，3！= 6，2！= 2，1！= 1，0！= 1

可用的数字集[1,2,3,4,5]

第一步：康托值=68，68/4！= 2，对于[1,2,3,4,5]数组的索引2是3，所以第一位是3。68%4！= 20，所以新的康托值是20，新的数组为[1,2,4,5]。

第二步：康托值=20，20/3！= 3，对于[1,2,4,5]数组的索引3是5，所以第二位是5。20%3！= 2，所以新的康托值是2，新的数组为[1,2,4]。

第三步：康托值=2，2/2！= 1，对于[1,2,4]数组的索引1是2，所以第三位是2。2%2！= 0，所以新的康托值是0，新的数组为[1,4]。

第四步：康托值=0，0/1！= 0，对于[1,4]数组的索引0是1，所以第四位是1。0%1！= 0，所以新的康托值是0，新的数组为[4]。

第五步：康托值=0，0/0！= 0，对于[4]数组的索引0是4，所以第五位是4。

即排列为[3,5,2,1,4]

逆康托展开c++代码

#include <iostream>
#include <vector>

using namespace std;

// 计算阶乘
int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; ++i)
        result *= i;
    return result;
}

// 逆康托展开：根据给定的字典序位置，推算出具体的排列
vector<int> inverseCantor(int n, int k) {
    vector<int> perm;            // 存储结果排列
    vector<int> nums;            // 可供选择的数字
    vector<bool> used(n + 1, false);  // 标记数字是否已使用

    // 初始化数字列表
    for (int i = 1; i <= n; ++i) {
        nums.push_back(i);
    }

    // 康托展开是 1-based，需要将 k 减去 1 转为 0-based
    k--;

    // 逐位计算每一位的数字
    for (int i = 0; i < n; ++i) {
        int fact = factorial(n - i - 1);   // (n - i - 1)!
        int idx = k / fact;                // 计算当前位应该选择哪个数字
        perm.push_back(nums[idx]);         // 添加数字到排列中
        nums.erase(nums.begin() + idx);    // 从数字列表中移除该数字
        k = k % fact;                      // 更新 k
    }

    return perm;
}

int main() {
    int n = 3, k = 4;  // 求第 4 个排列
    vector<int> result = inverseCantor(n, k);
    
    cout << "第 " << k << " 个排列是: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

四、力扣第60题 

虽然可以使用回溯法暴力枚举排列，但是很可能会超时。

比较好的方法是使用逆康托展开。

使用回溯法（力扣超时）

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void backtrack(vector<int>& nums, vector<bool>& used, string& item, vector<string>& res, int n) {
    if (item.size() == n) {
        res.push_back(item);  // 找到一个完整的排列
        return;
    }
    
    for (int i = 0; i < n; ++i) {
        if (used[i]) continue;  // 如果当前数字已经使用过，跳过
        item += to_string(nums[i]);  // 添加当前数字
        used[i] = true;  // 标记为已使用
        backtrack(nums, used, item, res, n);  // 递归生成下一个数字
        item.pop_back();  // 回溯，撤销选择
        used[i] = false;  // 取消标记
    }
}

string getPermutation(int n, int k) {
    vector<int> nums(n);
    vector<string> res;
    string item;
    
    for (int i = 0; i < n; ++i) {
        nums[i] = i + 1;  // 填充 [1, 2, ..., n]
    }
    
    vector<bool> used(n, false);  // 标记每个数字是否已使用
    backtrack(nums, used, item, res, n);  // 生成所有排列
    
    return res[k - 1];  // 返回第 k 个排列，注意 k 是 1-based
}

int main() {
    int n = 3, k = 3;
    cout << "第 " << k << " 个排列是: " << getPermutation(n, k) << endl;
    return 0;
}

使用逆康托展开

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string getPermutation(int n, int k) {
    // 预计算阶乘数组
    vector<int> factorial(n, 1);
    for (int i = 1; i < n; ++i) {
        factorial[i] = factorial[i - 1] * i;
    }

    // 初始化候选数字列表
    vector<int> nums;
    for (int i = 1; i <= n; ++i) {
        nums.push_back(i);
    }

    // k 是基于 1 的索引，所以减去 1 变成 0 基准索引
    --k;

    string result;

    // 按位构建第 k 个排列
    for (int i = n - 1; i >= 0; --i) {
        int idx = k / factorial[i]; // 确定当前位数字的索引
        result += to_string(nums[idx]); // 添加该数字
        nums.erase(nums.begin() + idx); // 从数组中移除该数字
        k %= factorial[i]; // 更新 k 的值，缩小范围
    }

    return result;
}

int main() {
    int n = 3, k = 3;
    cout << "第 " << k << " 个排列是: " << getPermutation(n, k) << endl;
    return 0;
}