全排列与康托展开：从火星人P1088到next_permutation的深入解析

我第一次看到 P1088 这道题时，第一反应是：NOIP 2004 普及组，名字叫"火星人"，这题应该不难吧？结果读题就绕了一下——火星人的计数方式不是十进制也不是二进制，而是用排列的顺序来表示数。题目本质其实一句话就能说清：给定一个 1 到 N 的排列，把它看作全排列字典序中的某一个位置，往后数 M 个，输出新的排列。这道题非常适合用来打通"全排列"这条知识线：从最直接的 STL 调用，到手写 next_permutation，再到康托展开和逆康托展开，层层递进，每一层都是能用在后续算法题里的硬通货。

如果你在洛谷上做题，或者在准备算法竞赛，这篇内容可以帮你彻底吃透全排列相关的几类经典操作。我把自己的完整思考过程、代码实现和一些提交时的低级错误都写在这里，适合从入门到进阶的读者参考。

1. 火星人的计数方式到底是什么：排列即数字

先说题目本身。火星人有 N 个手指，每个手指编号是 1 到 N，他们就靠这 N 个手指的顺序来记录一个正整数。换句话说，给定一个 [1, N] 的排列 a1, a2, ..., aN，这个排列本身就代表了一个数。那这个数是怎么定的呢？答案是：所有 N! 个排列按字典序从小到大排好，当前排列所在的位置就是它表示的数。

这个设定对第一次接触的人来说有点抽象，但用 N = 3 举例子就非常直观：

所以，题目输入一个当前的排列，再给一个 M，要你算出往后数 M 个之后是什么排列。比如输入排列是 2 3 1，对应数字 4，如果 M = 2，那么 4 + 2 = 6，对应的排列就是 3 2 1，这就是答案。

看明白这个例子之后就清楚了一个关键点：这个所谓"火星人的计数方式"，本质上就是全排列的字典序排名。你不需要真的去理解外星人的数学体系，只需要知道"在字典序序列中，从当前排列向后走 M 步"即可。这也意味着，所有全排列相关的算法都可以直接套用过来。

顺便说一句，题目里保证加 M 之后的结果一定合法，也就是说不会超过第 N! 个排列，所以不需要额外处理越界情况。不过即使不越界，你也得想清楚：一个排列的字典序排名的取值范围是 1 到 N!，而 N 可以到 10000，N! 是一个天文数字，根本不可能用普通整数存下来。这是后面所有设计的一个隐性约束。

2. 直接调用 next_permutation 为什么能轻松过题

拿到这道题，最简单粗暴的思路就是：既然要往后走 M 个排列，那就调用 M 次 next_permutation 不就行了？

我第一次做这题时也担心会不会超时，于是专门算了算复杂度。next_permutation 单次的时间复杂度是 O(N)，需要执行 M 次，所以总复杂度是 O(N * M)。题目中 N 的范围是 <= 10000，M 的范围比较小，典型情况只有 100 左右，那么 N * M = 10000 * 100 = 1000000，也就是一百万次操作。这个量级在现代 CPU 上就是毫秒级别，稳稳通过。

用 STL 的解法核心代码很短：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; while (m--) { next_permutation(a.begin(), a.end()); } for (int i = 0; i < n; i++) { if (i) cout << ' '; cout << a[i]; } cout << '\n'; return 0; }

这个解法在洛谷上能 AC，代码也短，但我必须提醒一个新手特别容易犯的错误：不要把输入排列先排序，然后从最小排列开始执行 M 次。题目给的是一个已经被指定的起点，你只能从它往后走，不能先回到最小排列再重新数，那样得到的结果和题目要求完全不是一回事。

举个例子：输入排列是 2 3 1，M = 2，从它往后走两步是 3 2 1（对应数字 6）。如果先排序成 1 2 3，再走两步变成 2 3 1，这就直接做错了。STL 的 next_permutation 是从当前排列本身出发，这正好符合题意，所以你直接用就行，千万别画蛇添足。

既然 STL 解法这么简单，那还有必要深挖吗？有，因为很多题目环境不允许你直接调 STL，或者你需要在这种极简操作背后理解它的运行原理。更重要的是，如果 M 的范围变大，或者 N 的范围变大，直接循环 M 次 next_permutation 就不一定扛得住了，这个我在后面第 4 节会专门展开。

3. 剖析 next_permutation：字典序下一个排列的完整推导

只会在代码里写 next_permutation(a.begin(), a.end()) 是不够的，面试和笔试题里经常要求你手写这个函数。理解它的原理一点都不难，关键是把字典序的规则想透。

字典序比较两个排列时，是从第一位开始逐个比较，找到第一个不同的位置，谁在这一位的数字小，谁就排在前面。这和英语词典里单词排序的规则一样，所以叫字典序。

那从当前排列找"字典序下一个排列"，逻辑上就是：在不改变尽量长前缀的前提下，把最后一个还能变大的位置变大，然后让后面的部分变成最小的排列。这样做得到的一定是下一个排列，因为任何改变更靠前的操作都会跳过多于一个排列。

具体分四步走：

1. 从右往左扫描，找到第一个满足 a[i] < a[i + 1] 的位置 i。这个位置就是"最后一个还能变大"的位置。
2. 在 i 的右边，找到最小的大于 a[i] 的数字 a[j]。
3. 交换 a[i] 和 a[j]。
4. 把 a[i + 1] 到末尾这一段反转。

这里要理解一个关键性质：从左往右看，第一次出现上升的边界是 i，也就是说，i 右边的序列一定是一个严格递减序列。所以第一步找到 i 后，右侧已经是从大到小排好的。第二步在递减序列中找第一个比 a[i] 大的数字即可，它就是"最小的大于 a[i] 的数字"。交换之后，右侧依然保持递减顺序。第四步把这段递减序列反转，得到递增序列，这正好是"右侧能形成的最小排列"。

举个例子，排列是 1 5 4 2 3：

• 从右往左，2 < 3，所以 i = 3，a[i] = 2；
• 右侧 [3] 中大于 2 的最小数字是 3，交换得到 1 5 4 3 2；
• 反转 i + 1 到末尾，也就是反转空区间，结果还是 1 5 4 3 2。

但这个例子太简单了，换一个更有意思的：排列 1 5 4 3 2：

• 从右往左，5 > 4，4 > 3，3 > 2，都递减，直到 1 < 5，所以 i = 0，a[i] = 1；
• 右侧 [5, 4, 3, 2] 中最小的大于 1 的数字是 2；
• 交换 1 和 2，得到 2 5 4 3 1；
• 反转 [5, 4, 3, 1]，得到 2 1 3 4 5。

所以 1 5 4 3 2 的下一个排列是 2 1 3 4 5。你可以数一下，1 5 4 3 2 是字典序第 119 个（0-based 排名），2 1 3 4 5 正好是第 120 个（即最后一个），完全对得上。

手写版本如下：

bool next_permutation_manual(vector<int>& a) { int n = (int)a.size(); int i = n - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; if (i < 0) return false; // 已经是最后一个排列 int j = n - 1; while (a[j] <= a[i]) j--; swap(a[i], a[j]); reverse(a.begin() + i + 1, a.end()); return true; }

注意几个边界：第一步找 i 的时候，条件是 a[i] >= a[i + 1] 就继续往前，等于是跳过所有递减部分；如果 i 变成 -1，说明整个排列完全递减，也就是没有下一个排列了，返回 false。第二步找 j 时，因为右侧是递减的，所以从末尾往左找到的第一个大于 a[i] 的数就是目标，不需要显式比较大小找"最小"，直接从右往左找就行。

说实话，手写一遍之后，你对 STL 的信任度都会上升一层，因为它内部实现基本就是这样，没有任何魔法。

4. 从"看似合理的优化"到康托展开与逆康托展开

等下，我上面说直接循环 M 次 next_permutation 能过题，但如果我告诉你，有人试着"只对排列末尾截取一段做 next_permutation"来优化，然后踩坑了，你会不会觉得意外？我当初就干过这事，还花了不少时间调试。

当时我的想法很直接：既然 M 很小，那排列的前面大部分位置根本不会变，只有最后某个长度的子序列在不断轮转。那是不是把最后 t 个数字截出来，只对这一小段做 M 次 next_permutation，前面保持不变，就能省下大量时间？

这个思路听着挺美，但有一个致命反例。比如排列 3 5 4 2 1，取后三位 4 2 1 做 next_permutation。4 2 1 是一个递减序列，已经是后三位能组成的最大排列，没有下一个了。可是整个排列 3 5 4 2 1 的下一个排列是 4 1 2 3 5，因为 4 2 1 无法继续变大时，进位到了更前面的 5，与 3 交换后重新整理了后缀。如果你只操作后三位，得到的是完全错误的结果。

这个反例说明：不能简单地"截取末尾固定长度"来做局部模拟，因为你判断不了当前截取段是否已经处于"局部最大"状态，一旦进位，影响范围就会向前扩展。

要严谨地解决这个问题，就得回到排列和序号的本质关系上来。这里引出康托展开和逆康托展开。

康托展开解决的是"给一个排列，求它是第几个排列"的问题。0-based 排名计算公式如下：

rank = ∑_{i=1}^{n} s_i × (n - i)!

其中 s_i 表示第 i 个位置右侧有多少个比 a[i] 小的数字。理解这个公式的关键在于逐位考虑：当你在第 i 位确定了数字 a[i] 之后，如果这一位没有填 a[i]，而是填了一个更小的数字，那么后面 (n - i) 个位置可以任意排列，每种排列都会让当前排列的排名变大 (n - i)! 个。

举个例子，排列 2 3 1：

• i = 1，a[1] = 2，右侧比 2 小的是 1，所以 s1 = 1，贡献 1 × 2! = 2；
• i = 2，a[2] = 3，右侧比 3 小的是 1，所以 s2 = 1，贡献 1 × 1! = 1；
• i = 3，a[3] = 1，s3 = 0；
• rank = 2 + 1 = 3（0-based），也就是说它是第 4 个排列，和前面表格里 2 3 1 对应数字 4 完全一致。

逆康托展开就是反过来：给定排名，还原排列。做法是维护一个候选数字列表，初始为 1 到 N，然后从高位到低位依次确定每一位的数字：

1. 令 rank_0 = rank - 1（如果排名是 1-based）；
2. 对于第 i 位，计算 idx = rank_0 / (n - i)!，从候选列表中取出第 idx 个数字（下标从 0 开始）；
3. 更新 rank_0 = rank_0 % (n - i)!；
4. 从候选列表中删除该数字，继续下一位。

看似和这道题关系不大？其实关系很大。回到火星人这道题，如果 M 不是 100 而是非常大的数，比如 10^18，那么循环 M 次 next_permutation 就完全不可能了。此时正解思路应该是：算出给定排列的排名 rank0，加上 M 得到新的排名 rank1，再用逆康托展开还原排列。

但问题来了，N 很大时 rank 会超过任何内置整数类型。解决思路是：不需要完整算出 rank0，只需要维护一个"变进制数"表示。观察康托展开公式，rank = s1 × (n-1)! + s2 × (n-2)! + ... + sn × 0!，这其实就是一个每位权值不同的变进制数，其中第 i 位的取值范围是 0 到 n - i。对 rank 加 M，等价于对这个变进制数加 M。

在这个变进制系统中做加法时，从低位向高位逐位处理：先把 M 拆成对应权值的分量，或者直接逐位加上并进位。M 是普通十进制整数，拆分的公式是：从低到高，依次取 m % k、m / k，k 从 2 开始递增，直到 m 变成 0。因为最低一位权值是 0! = 1，但这一位数恒为 0，实际从权值 1! 对应的位开始处理。

拆 M 例如 M = 5：

• 5 % 2 = 1，作为权值 1! 位的增量，5 / 2 = 2；
• 2 % 3 = 2，作为权值 2! 位的增量，2 / 3 = 0；
• 所以 5 = 1 × 1! + 2 × 2!，变进制表示的低位到高位是 [1, 2]。

然后把 M 的变进制分量加到原排列的康托展开分量上，处理进位，最后用逆康托展开还原排列。由于 M 的范围有限，涉及到进位的位数不会超过使 k! > M 的最小 k 太多，所以可以高效处理。不过这种写法代码量大很多，对本题来说是杀鸡用牛刀了。

我把康托展开的正向实现也贴一下，方便对照理解：

long long cantor(const vector<int>& a) { int n = (int)a.size(); vector<int> bit(n + 1); long long rank = 0, fact = 1; for (int i = n - 1; i >= 0; i--) { int smaller = 0; for (int j = i + 1; j < n; j++) { if (a[j] < a[i]) smaller++; } rank += smaller * fact; fact *= (n - i); } return rank; }

这里类比的思路是：把排列看成一本厚字典里的一个词，康托展开是查页码，逆康托展开是按页码翻词。火星人只是把这个"页码"当成了要计数的数字而已。

5. 完整代码与提交中的常见坑

回到这道题本身，我建议至少掌握两种提交写法：一种是直接依赖 STL，代码最短；一种是手写 next_permutation，遇到不能用 STL 的环境也不慌。下面是我本人在洛谷提交过的完整版本。

C++ 完整实现（短版本）：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } while (m--) { next_permutation(a.begin(), a.end()); } for (int i = 0; i < n; i++) { if (i) cout << ' '; cout << a[i]; } cout << '\n'; return 0; }

C++ 完整实现（手写 next_permutation 版本）：

#include <bits/stdc++.h> using namespace std; bool nextPermutation(vector<int>& a) { int n = (int)a.size(); int i = n - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; if (i < 0) return false; int j = n - 1; while (a[j] <= a[i]) j--; swap(a[i], a[j]); reverse(a.begin() + i + 1, a.end()); return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } while (m--) { nextPermutation(a); } for (int i = 0; i < n; i++) { if (i) cout << ' '; cout << a[i]; } cout << '\n'; return 0; }

Python 完整实现：

import sys def next_permutation(a): n = len(a) i = n - 2 while i >= 0 and a[i] >= a[i + 1]: i -= 1 if i < 0: return False j = n - 1 while a[j] <= a[i]: j -= 1 a[i], a[j] = a[j], a[i] a[i + 1:] = reversed(a[i + 1:]) return True def main(): data = sys.stdin.read().split() n = int(data[0]) m = int(data[1]) a = list(map(int, data[2:2 + n])) for _ in range(m): next_permutation(a) print(" ".join(map(str, a))) if __name__ == "__main__": main()

提交这道题的过程里，我踩过几个特别蠢但也很典型的坑，罗列在这里，给大家提个醒：

第一个坑是输入顺序。题目先给 N，再给 M，最后给排列。有人会习惯性先读 M 再读 N，或者把排列的长度读错，结果后面一系列数组越界。这种题考查的不是读入，读入错了是真的冤枉。建议写完代码后先看一眼样例，确保输入变量对应正确。

第二个坑是输出格式。要求是输出 N 个数，数字之间用空格分隔，末尾有没有多余空格一般不影响判定。但如果你输出成每个数字一行，那就会直接 WA。还有人在最后少输出了换行，虽然很多判定程序容忍末尾没有换行，但保险起见还是加上。

第三个坑是"循环 M 次 next_permutation"里的边界。如果 M 是 0，循环一次都不执行，直接输出原始排列，这个逻辑在代码里天然正确，不用特殊处理。但如果用 while (m--) 这种写法，m 会被减到负数，之后再用 m 就会出问题。这道题里 m 用完就不用了，所以没事；但如果你后面还有用到 m，建议用 for 循环。

第四个坑是手写 next_permutation 时容易在找 j 的地方写错。因为在 i 右侧是递减序列，所以从右往左找到的第一个大于 a[i] 的数就是目标，不需要额外变量去维护"当前最小的大于 a[i] 的数"。但如果你的环境不是递减序列（比如你错误的实现导致右侧没被反转），那就可能选错交换对象。所以手写时一定要确保前面找 i 的逻辑完全正确：左侧跳过的部分必须是 a[i] >= a[i + 1]，不能是 a[i] > a[i + 1]。用 >= 还是 > 很关键，遇到有重复元素时区别特别明显。虽然这道题的排列是 1 到 N 的全排列，没有重复元素，但为了写出通用性更强的代码，我建议还是用 >=。

第五个坑是关于复杂度的心理预期。有些人看到 N = 10000，就以为 O(N * M) 过不了，非得去搞康托展开，结果把自己绕晕。实际上 10000 * 100 = 1e6 这个量级非常小，根本不需要担心。真正需要担心的反而是数组开小、递归爆栈、输入输出没加速这类基础问题。

还有一个小技巧：如果你在做题时想验证自己的结果对不对，可以拿 N = 3、N = 4 的小数据手动枚举所有排列，然后跑代码对照。比如 N = 3 的全部排列是 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1，拿任意一个起点和 M 值手推一遍，再和程序输出比，基本能确认算法没问题。

最后再分享点个人感受。P1088 这道题虽然名字唬人，但它其实是全排列领域里最好的入门题之一。从 STL 调用入手，你可以一路延伸到手写 next_permutation，再到康托展开、逆康托展开，最后甚至能理解变进制数是怎么运作的。很多看起来复杂的排列计数问题，追根溯源都是这套东西。我后来在 Codeforces 上遇到一道 "Permutation" 相关的题，第一反应就是想起这道火星人，直接用逆康托展开的思路做出来了。所以别嫌弃它简单，把它吃透，后面的路会顺很多。