康托展开与逆康托展开算法详解

1. 排列顺序问题解析

今天我们来探讨一个经典的算法问题——排列顺序的生成与查找。这个问题在编程竞赛和算法面试中经常出现，核心是理解排列的字典序规律以及如何高效地进行排列生成和查找。

排列顺序问题通常有两种形式：

1. 给定n和k，生成第k个字典序排列
2. 给定n和一个排列，找出它在所有排列中的字典序位置

理解这个问题的关键在于掌握"康托展开"和"逆康托展开"这两个数学工具。它们就像排列世界的经纬度系统，让我们能在排列和序号之间自由转换。

2. 康托展开与逆康托展开原理

2.1 逆康托展开：从序号到排列

逆康托展开的过程就像拆解一个多层密码锁。假设我们要找n个数字的第k个排列：

1. 初始化可用数字列表vis=[1,2,...,n]
2. 对于第i位（从0开始）：
   • 确定当前位的数字在剩余数字中的位置：index = k / (n-1-i)!
   • 从vis中取出第index个数字作为当前位
   • 更新k = k % (n-1-i)!
   • 从vis中移除已选数字
3. 重复直到所有位确定

注意：实际编码时k需要减1，因为通常k从1开始计数而索引从0开始

2.2 康托展开：从排列到序号

康托展开则是逆过程，计算一个排列在所有排列中的字典序位置：

1. 初始化可用数字列表vis=[1,2,...,n]和结果k=1
2. 对于排列中的每个数字nums[i]：
   • 在vis中找到nums[i]的位置index
   • k += index * (n-1-i)!
   • 从vis中移除nums[i]
3. 最终k即为该排列的序号

这个过程的本质是计算有多少个排列比当前排列小，通过逐位比较累加得到总数。

3. 算法实现详解

3.1 预处理阶乘值

cpp复制const int N=21;
long long pre[N];

void init(){
    pre[0]=1;
    for(int i=1;i<N;i++){
        pre[i]=pre[i-1]*i;
    }
}

我们预先计算并存储0到20的阶乘值，因为n的最大值是20，20!在long long范围内。这种预处理避免了重复计算，提升了效率。

3.2 逆康托展开实