康托展开
学习是一个持续的过程，每一小步都是进步。
———— 未知
1. 定义
康托展开是一种将全排列映射到唯一自然数的双射算法（即一一对应，无重复、无遗漏）。
简单来说，它能给每一个 n 位全排列分配一个独一无二的“序号”，这个序号代表该排列在所有按字典序排列的全排列中的位置。
康托展开的核心价值在于：
- 实现全排列的空间压缩：将长度为 n 的排列（需要 n 个存储单元）转化为一个自然数（仅需 1 个存储单元）。
- 可逆性：逆康托展开。
2. 原理与推导
2.1 核心思想
对于一个 n 位全排列 a[1...n]，其康托展开值（即字典序排名）的计算逻辑是：
对排列的每一位 a[i]，统计在它之后比它小的数字的个数，乘以 (n-i)!（剩余位数的阶乘），将所有位的结果累加后加 1（排名从 1 开始，而非 0）。
公式表示：
\[X = \sum_{i=1}^{n-1} (k_i \times (n-i)!) + 1
\]
其中 \(k_i\) 是第 i 位之后比 \(a[i]\) 小的数字个数。
2.2 推导
以排列 3 4 1 5 2（n=5）为例，分步计算其康托展开值：
| 位置 i | 数字 a[i] | 后面比 a[i] 小的数字 | \(k_i\) | 剩余位数 | \((n-i)!\) | 贡献值 \(k_i \times (n-i)!\) |
|---|---|---|---|---|---|---|
| 1 | 3 | 2 | 4 | 24 | \(2 \times 24 = 48\) | |
| 2 | 4 | 2 | 3 | 6 | \(2 \times 6 = 12\) | |
| 3 | 1 | {} | 0 | 2 | 2 | \(0 \times 2 = 0\) |
| 4 | 5 | 1 | 1 | 1 | \(1 \times 1 = 1\) | |
| 5 | 2 | 无后续数字 | - | 0 | 1 | 无需计算 |
累加所有贡献值：\(48 + 12 + 0 + 1 = 61\)，加 1 后最终排名为 \(62\)，即 3 4 1 5 2 是 5 位全排列中字典序第 62 个排列。
3. 代码实现与解析
#include<bits/stdc++.h>
using namespace std;// 预定义阶乘数组：factorial[k] 表示 k!，覆盖0!到10!（满足10位排列需求）
const int factorial[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}; int cantor(int a[], int n) {int ans = 0, sum = 0; // ans存储累加结果，sum统计当前位后更小数字的个数// 遍历第1位到第n-1位（最后一位无后续数字，无需计算）for (int i = 1; i < n; i++) {// 统计第i位之后比a[i]小的数字数量for (int j = i + 1; j <= n; j++) {if (a[j] < a[i]) {sum++;}}// 累加当前位的贡献值：sum * (n-i)!ans += sum * factorial[n - i];sum = 0; // 重置计数器，准备统计下一位}return ans + 1; // 排名从1开始，因此加1
}int main() {int perm[12], len; // perm存储排列（最多支持10位），len：排列长度cin >> len;for (int i = 1; i <= len; i++) {cin >> perm[i];}cout << cantor(perm, len) << '\n';return 0;
}