前段时间刷题时遇到一个很有意思的问题给定数字集合把所有排列按字典序排好第 17086 个排列是什么很多人第一反应是把全排列全部生成出来再排序取第 17086 个。但真的有必要吗9 个数字的全排列有 362880 种如果 n 变成 12这个数字是 479001600直接爆内存。真正懂行的人会用数学方法在 O(n^2) 甚至 O(n log n) 的时间里直接定位答案。这篇博客不打算讲玄乎的理论就围绕“17086 字典序的全排列”展开把全排列、字典序、康托展开和逆康托展开这几个核心概念一次性讲透。你不需要很强的数学基础只需要会一点代码跟着我的计算过程走一遍以后遇到“第 k 个排列”“某个排列排第几”这类问题基本就能秒杀。1. 题目拆解17086 到底在问什么1.1 全排列从排队照相说起先回到基础概念。所谓全排列就是把一组元素的所有排列方式全部列出来。比如 3 个不同的人去排队拍照一共有 3! 6 种排法123、132、213、231、312、321。有 n 个互不相同的元素全排列数量就是 n 的阶乘。这里有个很容易被低估的点阶乘增长速度极其恐怖。9! 36288010! 362880011! 3991680012! 479001600。这意味着当 n 稍微变大一点暴力枚举全排列就立刻不现实了。9 个元素生成 36 万个排列还能接受12 个元素生成 4.79 亿个排列光存储和遍历就是灾难。所以涉及全排列的题目核心从来不是“能不能暴力”而是“怎么聪明地避免暴力”。如果给你 1 到 9 九个数字全排列总量是 362880。“17086 字典序的全排列”这个说法本质是在问在 1 到 9 这 362880 个按字典序排列好的排列中第 17086 个是哪一个。你也可以理解成有一本很厚的字典里面按字母顺序写满了所有 9 位互不重复的数字串你翻到第 17086 页看到的是什么。1.2 字典序排列世界的“英语字典”字典序这个概念可以类比英文字典。abc 排在 abd 前面因为前两位相同到第三位 c d。对数字串来说规则一样从左往右逐位比较碰到第一处不同的数字小的那个串排在前面。比如 123456789 123456798因为前 7 位相同第 8 位 8 9。全排列问题的排序规则如果不指定生成顺序千奇百怪。比如交换法生成的排列顺序就不一定是字典序。而 LeetCode、力扣上大量排列类题目默认使用字典序因为它有两个天然好处一是结果唯一所有排列有一个确定的总顺序二是不依赖生成算法不管你怎么生成的排列最后只要按字典序排结果一致。所以研究全排列时字典序几乎是最常用的“排序基准”。1.3 一个数字引出三类经典问题“17086 字典序的全排列”这个题目可以拆成三个层层递进的问题覆盖了算法面试的高频考点给定 n 和 k直接求字典序第 k 个排列不需要生成全部排列。这是力扣第 60 题的原型。给定一个排列反过来求它在字典序中的排名。这就是康托展开。生成全部排列然后按字典序排序或直接按字典序逐个产出。这个用回溯法或库函数解决。很多人刷题时只背了第 60 题的模板压根不明白里面的除法、取余、阶乘到底在干嘛。一旦题目从“求第 k 个”变成“求排名”就懵了。我希望通过 17086 这个具体数字把这三个问题串成一条线让你既看得懂代码也算得出过程。2. 全排列生成从回溯暴力到一行库函数2.1 回溯法最基础也最容易写错的全排列生成生成全排列最通用的方法是回溯。思路很朴素第一个位置放哪个数、第二个位置放哪个数、依次放完所有位置。用一个 visited 数组记录哪些数字已经被用过每次递归往前一步回溯时把状态撤销。def permute(nums): res [] path [] used [False] * len(nums) def dfs(): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) dfs() path.pop() used[i] False dfs() return res这段代码有三个细节值得注意。第一path[:] 必须写切片拷贝。如果直接 append(path)后续 path.pop() 会把已经存进结果的对象也改掉最后 res 里全是同一个列表。这个坑我见过无数人踩。第二used 数组标记的是“位置”而不是“数值”。当输入包含重复数字时同一数值可能出现两次必须配合排序加剪枝来去重否则生成一堆重复排列。第三回溯顺序和字典序的关系如果 nums 本身有序且循环按索引递增顺序尝试那么生成的排列确实是字典序。如果 nums 无序生成结果就不是字典序。很多人忽略这一点后面我会详细分析。回溯法的时间复杂度是 O(n * n!)空间复杂度是 O(n) 递归深度加上 O(n * n!) 的结果存储。注意这个结果存储才是最大的开销。n 9 时还好n 10 时存储 3628800 个元组内存可能直接飙升到数百 MB。2.2 Python 的 itertools.permutations能用但别滥用如果你只是快速验证思路Python 的 itertools.permutations 一行就能解决问题from itertools import permutations nums [1, 2, 3, 4, 5, 6, 7, 8, 9] perms list(permutations(nums)) print(perms[17085]) # (1, 5, 4, 8, 3, 9, 6, 7, 2)注意索引是 17085因为列表下标从 0 开始第 17086 个元素的下标是 17085。permutations 在输入有序的前提下会按字典序逐个产出排列这是官方实现保证的行为。这也是最直观拿到第 17086 个排列的方式。但面试或竞赛中直接用库函数要谨慎。一是标准库未必在所有环境都可用二是面试官问你“下一个排列怎么实现”时一句 imports permutations 大概率不能过关。更重要的是permutations 仍然要生成所有排列或者至少迭代到目标位置时间复杂度 O(n!)。n 12 时光迭代到第 4.79 亿个排列这个耗时就已经无法接受了。所以我的建议是日常验证、写脚本可以用库函数学原理、刷题、应对性能要求时必须理解手写实现。2.3 交换法和 next_permutation两个容易混淆的方向全排列还有一个经典写法交换法。每次把当前元素和后面的元素交换然后递归处理剩余部分。def permute_swap(nums, start0, resNone): if res is None: res [] if start len(nums): res.append(nums[:]) return for i in range(start, len(nums)): nums[start], nums[i] nums[i], nums[start] permute_swap(nums, start 1, res) nums[start], nums[i] nums[i], nums[start] return res交换法空间复杂度低不需要额外 visited 数组但它生成的排列顺序存在一个致命问题默认不是字典序。拿 1、2、3 试一下输出顺序是 123、132、213、231、321、312最后两组 321 和 312 明显不满足字典序。如果你把交换法的结果直接当成字典序全排列做“求第 k 个排列”的题目时就会出错。真正常用于字典序的工具是 next_permutation 算法。它的使命不是生成顺序任意的排列而是“从当前排列出发得到字典序中的下一个排列”。手写版本很经典def next_permutation(nums): i len(nums) - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: return False j len(nums) - 1 while nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] nums[i 1:] reversed(nums[i 1:]) return True这个算法的思想用一句话概括从右往左找到第一个“上升点”然后把它替换成右侧比它大的最小元素最后把后面那段反转成升序。比如 154839672 的下一个排列是什么用这个算法跑一遍你能看到它精准地找到下一个字典序排列而不是像交换法那样乱序。全排列和 next_permutation 是“一对”前者生成所有排列后者按字典序一步步推进。如果只需要二进制递增效果两个都可以如果需要严格字典序且不想一次性生成全部next_permutation 是首选。3. 求第 17086 个排列逆康托展开实战3.1 核心思路像查字典一样定位现在回到核心问题求字典序第 17086 个排列。最简单但最笨的思路是生成全部 362880 个排列再取第 17086 个。n 9 时勉强能忍n 10 时就会卡顿n 12 时彻底歇菜。高效做法叫逆康托展开它的核心思想是“分块定位”。打个比方一本厚字典里单词按字母顺序排列你想找第 17086 个词不需要从第 1 个翻到第 17086 个而是可以按字母桶去跳第一页到第 40320 页全是字母 a 开头17086 没超过 40320所以目标一定在 a 桶里拿起 a 桶再看第二位字母每个第二位字母对应 5040 页……这样不断缩小范围最终直接锁定目标单词。具体到数字排列1 到 9 的全排列第一位固定为 1 的排列有多少个固定第一位后剩下 8 位可以任意排列数量就是 8! 40320。所以排列按字典序分组后每 40320 个一组共 9 组。第 17086 个排列肯定落在第一组也就是以 1 开头。因为 17086 ≤ 40320所以第一位直接确定为 1。然后处理第二位。位置已经消耗掉一位剩余 8 个数字其中每一项再按第二位分组每组数量是 7! 5040。用当前剩余排名对 5040 做除法得到组号就能确定第二位。这个过程一直重复到所有位置填满。你发现没这个操作本质上就是一个“不断除阶乘、取商、取余”的过程和进制转换有异曲同工之妙。3.2 逆康托展开原理为什么除法能定位逆康托展开的数学基础很朴素。设当前剩余可选数字集合大小为 m当前要决定排列第 i 个位置的数字。剩余 m - 1 个数字的全排列数量是 (m-1)!也就是说当前位置每跳过一个可选数字就跳过了 (m-1)! 个排列。于是把“当前排名”除以 (m-1)!商就是应该选择剩余数字中从小到大第几个余数则用于决定后续位置。写成公式对于 n 个互异元素的全排列在从 0 开始计数的排名 r 下第 i 位应选取剩余集合中下标为r // (n-1-i)!的元素同时更新r r % (n-1-i)!。不断重复直到所有位填满。注意这里有个极其容易混淆的细节排名从 0 开始还是从 1 开始。如果题目说“第 k 个排列”通常 k 从 1 开始那么编程时第一步要做r k - 1。力扣第 60 题就是这样。我见过太多人在这里出错有的忘了减 1有的减了又加回去最后答案差了一位还不自知。下面整个推演过程我都用从 1 开始的“第 17086 个”转成 0 开始的排名就是 17085。3.3 手把手推算从 17085 到 154839672下面我们把整个计算过程完整走一遍。为方便阅读我整理了一张分步表每一步的“当前 k”都是 0 开始计数的排名阶乘 f 是当前位置的权值。步骤剩余可选数字阶乘 f当前 k商 idx选中数字更新 k1[1,2,3,4,5,6,7,8,9]8! 403201708501170852[2,3,4,5,6,7,8,9]7! 5040170853519653[2,3,4,6,7,8,9]6! 7201965245254[2,3,6,7,8,9]5! 12052548455[2,3,6,7,9]4! 244513216[2,6,7,9]3! 6213937[2,6,7]2! 231618[2,7]1! 111709[2]0! 10020我来把关键步骤的口算拆开过程讲一遍确保你能完全对上。第一步17085 除以 40320商 0 余 17085所以选剩余数字中下标 0 的数字 1。这一步说明了目标排列在以 1 开头的 40320 个排列里。第二步剩余数字 [2,3,4,5,6,7,8,9]k 仍是 17085。17085 除以 5040商 3 余 1965。商 3 的意思是以 12 开头的有 5040 个以 13 开头的有 5040 个以 14 开头的有 5040 个这三个块共 15120 个排列全部小于目标排列。所以目标排列跳到下标 3也就是数字 5。当前剩余 k 是 17085 - 15120 1965。第三步剩余 [2,3,4,6,7,8,9]。1965 除以 720商 2 余 525。前面以 152 开头和 153 开头的两块共 1440 个小于目标所以选择下标 2 的数字 4。当前 k 525。到这里前三位是 154。第四步剩余 [2,3,6,7,8,9]。525 除以 120商 4 余 45。跳过四个块对应下标 4 的数字 8。前四位 1548。后面每一轮都如法炮制最终依次得到 3、9、6、7、2完整结果 154839672。你可能会问为什么第二步商 3 对应数字 5而第三步商 2 对应数字 4下标和数字之间怎么对不上因为这里的下标是“剩余数字列表”的下标不是全局数字本身。剩余列表 [2,3,4,6,7,8,9] 中下标 2 才是数字 4。每次选完一个数字它就从列表里删除列表越来越短所以下标含义也随之变化。这一点只要自己做一次计算就会印象非常深刻。3.4 代码实现逆康托展开的标准写法这里给出一个干净、可直接用的逆康托展开实现def kth_permutation(nums, k): # k 从 1 开始计数返回第 k 个字典序排列 nums sorted(nums) n len(nums) fact [1] * n for i in range(1, n): fact[i] fact[i - 1] * i if k 1 or k fact[-1] * n: raise ValueError(k 超出全排列总数范围) r k - 1 res [] for i in range(n): f fact[n - 1 - i] idx r // f res.append(nums.pop(idx)) r % f return res print(kth_permutation([1, 2, 3, 4, 5, 6, 7, 8, 9], 17086)) # [1, 5, 4, 8, 3, 9, 6, 7, 2]这段代码里有几个细节值得关注。nums sorted(nums)是必须的因为字典序默认是在元素本身有序的前提下谈论的。如果原数组是 [9, 3, 1, 7, 5, 2, 8, 4, 6]你不排序直接算结果完全错误。fact 数组预计算到 n-1 的阶乘避免循环里反复算阶乘浪费时间。严格来说我们只需要到 (n-1)!但为了方便统一数组长度我开成 n 个元素最后一位是 (n-1)!。还有一种写法是只算到 n-1然后下标统一用fact[n - 1 - i]。参数检查容易被忽略。k 合法范围必须是 1 到 n!。比如 n 3 时 k 7 就是非法输入因为只有 6 个排列。如果 k 从 0 开始那合法范围是 0 到 n! - 1。两种习惯都对但一个程序里必须统一否则第二步的除法会得到越界下标。选数字用的是nums.pop(idx)每个元素只会被选一次。pop 操作是 O(m)整个算法时间复杂度 O(n^2)。n 一般不到 20所以完全够用。如果 n 很大可以用树状数组或平衡树把“选剩余第 idx 小元素”优化到 O(n log n)但实际场景里很少遇到先掌握 O(n^2) 版本就够了。4. 给定排列求排名康托展开与验证4.1 原理把分块思想倒过来逆康托展开解决的是“排名到排列”反过来就有康托展开给定一个排列求它在字典序中的排名。这是 17086 这道题验证答案、也验证你理解的关键一步。康托展开的思想同样很直观逐个看排列每一位数字统计“当前剩余数字中比这一位小的数字个数”把这个数量乘上右侧剩余位置的阶乘累加到一个变量里最后加 1 就是排名。为什么加 1因为累加出来的数表示“比当前排列小的排列有多少个”。比如最小的排列 123456789每一位都比它小的数字个数都是 0累加和是 0排名是 0 1 1。最大排列 987654321累加和是 362879加 1 得到 362880恰好是最后一个。再次强调康托展开中“比当前位小且还没使用”这一条件很重要。不能简单统计“原始数字中比它小的总数”否则重复计算了前面已经选走的数字。必须动态维护一个剩余数字集合。4.2 验证 154839672 的排名等于 17086下面用完整表格验证上节的答案。排列是 1, 5, 4, 8, 3, 9, 6, 7, 2剩余集合从 [1..9] 开始每步移除当前数字。位置当前数字当前剩余集合剩余中比当前数字小的数量阶乘权值贡献11[1,2,3,4,5,6,7,8,9]08! 40320025[2,3,4,5,6,7,8,9]3 (2,3,4)7! 50401512034[2,3,4,6,7,8,9]2 (2,3)6! 720144048[2,3,6,7,8,9]4 (2,3,6,7)5! 12048053[2,3,6,7,9]1 (2)4! 242469[2,6,7,9]3 (2,6,7)3! 61876[2,6,7]1 (2)2! 2287[2,7]1 (2)1! 1192[2]00! 10把贡献列全部加起来0 15120 1440 480 24 18 2 1 0 17085排名 17085 1 17086。看到没有逆康托展开得到 154839672再对 154839672 做康托展开又回到 17086。这两个操作互为逆运算一个从排名到排列一个从排列到排名。当你自己手工推完这两个过程后再去看网上任何一份康托展开模板都会觉得非常亲切。4.3 编码实现与数值细节康托展开的实现比逆展开更简单。重点仍是维护“剩余数字集合中比当前数字小的数量”可以直接用列表加循环统计def perm_rank(nums, perm): nums sorted(nums) n len(nums) fact [1] * n for i in range(1, n): fact[i] fact[i - 1] * i rank 0 for i in range(n): cnt 0 for x in nums: if x perm[i]: cnt 1 rank cnt * fact[n - 1 - i] nums.remove(perm[i]) return rank 1 print(perm_rank([1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 5, 4, 8, 3, 9, 6, 7, 2])) # 17086这个版本下统计 cnt 的小循环每次遍历剩余数字列表remove 也是 O(n)整体 O(n^2)。如果 n 较大可以维护一个树状数组每个数字用 1 标记“还在剩余集合中”查询“小于当前数字的剩余数量”就是一次前缀和复杂度降到 O(n log n)。但这是优化题基础版本能理解并写对就够应付绝大多数面试。还有两个细节必须提醒。一是阶乘表依然建议预计算不要每次位置都重新算阶乘。二是当 n 较大、接近 20 时排名数值会超过 64 位整数的范围。20! 2432902008176640000约 2.4e18还在 64 位有符号整数范围内但 21! 已经超了。如果题目不做特殊说明通常 n 会被限定在 9 或 10 这种小范围用 Python 的整数无所谓用 C 时就要小心 long long 溢出必要时用大数库或模运算处理。5. 实操中的常见问题与避坑指南5.1 下标混乱第 1 个还是第 0 个这是全排列相关题目里最经典、最容易错的点。康托展开返回的排名多数情况下约定从 1 开始计数因为业务和题目描述通常说“第 k 个”。但逆康托展开内部又必须用从 0 开始的计数来处理除法定位。很多初学者在这两者间来回切换时晕头转向。我的经验是死记一条铁律外部接口用“第 k 个”内部计算用“0 开始排名 r”所有逻辑从r k - 1开始。写代码时不要在多个地方来回加 1 减 1只在入口做一次转换。如果你发现自己的代码里有好几处 1或者- 1大概率是算法没想清楚在打补丁。停下来重新理一遍通常能删掉一半的别扭代码。5.2 有重复元素时怎么办前面讲的全是 n 个互不重复元素。如果输入是 [1, 1, 2, 3]事情就变得复杂了。此时全排列总数不再是 4! 24而是 4! / 2! 12因为两个 1 互相交换后排列不变。针对重复元素纯数字的康托展开公式需要改成多重集排列的方式。以排列 [1, 2, 1, 3] 为例处理第一位 1要统计比 1 小的数字中还没有被使用的元素个数。由于存在重复值比当前值小的所有候选必须以多重集排列方式计算贡献假如候选数字 d 出现过 c_d 次并可全部使用把 d 放到当前位置后剩余位置的全排列数是“剩余数字总量 - 1”的阶乘除以各数字剩余次数的阶乘。实际操作中更稳妥的做法是先把重复元素归并成“数值 剩余次数”的列表然后在每个位置枚举“可以放在当前位的小数值”用多重集排列公式计算跳过的排列数。这个方法比直接对原始数组做康托展开安全得多因为原始数组里两个相同值会各自带一个位置标记导致同一个排列被当作用不同怪位置排列算出多个不同排名。简单说遇到重复元素不要照抄普通康托展开模板。先想清楚是用去重后的多重集公式还是干脆换一种方式处理排名。我见过大量算法题解在这块含糊其辞实际写代码时很容易踩坑。5.3 生成顺序不对交换法不等于字典序前面提过交换法生成的全排列顺序不是字典序。如果你手头有现成的交换法全排列代码想看第 17086 个排列拿到第 17086 个生成的排列直接当答案必错。正确做法要么改用 next_permutation 反复调用 17085 次要么先把全部排列收集起来按字典序排序要么直接上逆康托展开。这里补充一个既简单又不容易错的折中方案用回溯法生成但保证循环按“数值从小到大”的顺序尝试未使用数字。这本质上就是按字典序生成。它比交换法多一个 visited 数组却省去了排序的麻烦。另外C 的 std::next_permutation 会原地修改数组并在无法生成下一个时返回 false。刷题时很多同学用它做全排列枚举写法是sort(nums.begin(), nums.end()); do { // 处理当前排列 } while (next_permutation(nums.begin(), nums.end()));这里必须先 sort否则枚举的不是完整字典序全排列。很多同学漏了 sort导致输出从某个中间状态开始数量也少了查错查得非常痛苦。5.4 性能对比暴力生成和数学方法差多少我实际测试过一个直观场景n 9生成全部 362880 个排列并取出第 17086 个。用 Python 回溯法大约需要数十毫秒到上百毫秒取决于机器内存需求同样明显。用 itertools.permutations 推流到第 17086 个耗时更短但也需要线性扫过 17086 个排列。用逆康托展开几乎瞬间完成因为总共只有 9 轮循环和列表操作。当 n 12 时差距就更夸张了。暴力生成全部排列需要 4.79 亿个每个排列至少要存 12 个数字内存需要几个 GB几乎不可行。逆康托展开依然是 12 轮循环耗时可以忽略不计。我整理了一个粗略对比表帮你建立直观感受n全排列总数暴力生成全部排列直接遍历到第 k 个逆康托展开6720可忽略快快9362880约 0.1 秒级快微秒级103628800秒级且内存压力大可以但没必要微秒级12479001600不可行不可行微秒级所以结论很明确如果题目明确要求“第 k 个排列”或“某个排列的排名”第一反应应该是康托展开家族而不是全排列生成。生成全排列这个操作只适用于 n 很小、需要穷举所有方案的场景。6. 这类问题在实际场景中的应用6.1 算法竞赛中的高频考法康托展开和逆康托展开在算法竞赛里算是经典入门偏进阶的组合题。举几个常见的出题方向一是构建“排列 ↔ 排名”的互相映射用于状态压缩或搜索判重。比如八数码问题、数独求解中有时需要把一个排列状态映射成一个整数康托展开就提供了完美的空间压缩方式。一个 9 位排列用 362880 以内的整数表示比直接存数组省太多内存。二是配合树状数组做动态排名查询。前面提到的“剩余集合 前缀和”优化本质是动态维护一个 01 数组并频繁查前缀和这几乎是树状数组最经典的入门应用。三是作为下一排列问题的延伸。给定两个排列求它们之间有多少个排列或者在字典序中相差多少位这类题可以直接用康托展开把两个排列都转成排名再做减法。理解了 17086 这个例子后这种题目基本套公式即可。力扣上和这个知识点直接相关的题目包括第 46 题全排列、第 47 题全排列 II、第 31 题下一个排列、第 60 题第 k 个排列。刷完这几道再把康托展开和逆康托展开的模板练熟该方向就没什么死角了。6.2 实际业务中的排列组合思路别觉得这只是竞赛题。业务代码里也有不少地方能借鉴这个思路。比如生成不重复的短码。假设你要为一批订单生成 6 位不重复的随机邀请码可以从所有可用字符的全排列中随机选一个排名再利用逆康托展开得到一个唯一排列。这种方式比每次随机生成再查重更可控因为排名和编码是一一对应的。当然字符集扩大后全排列数量暴涨实际场景会更倾向于直接用自增 ID 映射混淆编码但思路是相通的。再比如权限角色的排列组合测试。给系统配置一组权限策略需要按字典序枚举所有可能性去跑自动化测试用 next_permutation 或者康托展开都可以做到“可续传”记录当前处理到哪个排名下次继续从该排名恢复而不用从头生成。这个特性在长任务分布式处理中很实用。还有抽签、排序算法的随机化。Knuth shuffle 是洗牌的标准做法但从字典序角度也可以先随机一个排名再用逆康托展开得到随机排列。由于全排列总数可能极大直接用排名到排列的映射在某些硬件受限场景反而有优势因为它避免了反复 swap 操作。6.3 变种与延伸从排列到组合一旦吃透了康托展开的“分块定位”思想你会发现它还能推广到组合问题。组合同样有字典序比如从 5 个数里选 3 个按字典序排列组合也存在着“给定组合求排名”和“给定排名求组合”的互逆操作。原理相似当前位置枚举一个数后跳过的是 C(剩余数字个数, 剩余位置数) 个组合而不是阶乘。这种推广思路很值得自己推一遍。当你遇到“字典序第 k 个子集”“字典序第 k 个组合”之类的题目就不再需要把全部组合生成出来再排序了。可以说康托展开是“字典序世界”里一把万能钥匙排列通、组合通、子集也能通。7. 个人体会与一点建议我第一次认认真真手算 17086 这个排列的时候算到一半其实有点怀疑人生又是 5040 又是 720这不是折腾人吗但当 154839672 这个结果完整出来再用康托展开反查回去精确地得到 17086 的那一刻确实有“原来如此”的通透感。那种感觉不是背模板能带来的。后来我把这个思路用在树状数组优化、多重集康托展开、组合字典序上发现所有代码都像是从同一个“分块定位”思想里长出来的。所以我会建议你把这篇推演过程自己完整写一遍不要复制代码拿张纸把 1 到 9、17086 这两个数字放进表格里一步步算。算错了也没关系恰恰是哪里算错哪里就是你理解还没到位的地方。题目本身只是一个数字但“17086 字典序的全排列”背后的分块、阶乘、互逆映射才是真正值得反复咀嚼的东西。刷题有时候就是这样一道题吃透了一类题都会了。希望你也能从这次推演里拿到属于自己的那个“原来如此”。
