这道题我印象挺深的是我入门DFS时手写过的第一道“有点意思”的题给定一个由 1~n 组成的排列让你算出它在所有排列里按字典序排第几个。比如 n3排列 2 3 1 是第 4 个。题目名称直接就叫“深度优先搜索(DFS)练习1——排列序数”一看就知道是拿来练 DFS 的。如果你刚学 DFS经常遇到“知道要递归、也背过模板但一写就乱”的情况那这篇就是你的参考。我会从问题拆解、状态设计、代码实现一路讲到调试心得和康托展开验证最后还会列一些新手必踩的坑。整个过程我会带着实际代码和手推过程走一遍而不是只讲概念。1. 先搞清楚我们在练什么排列序数问题1.1 题目到底在问什么题目通常会这样描述输入一个正整数 n然后是 1 到 n 的一个排列每个数字恰好出现一次要求输出这个排列在 1~n 所有全排列中按字典序从小到大排序后的位置。位置从 1 开始计数。举个例子n3所有排列按字典序从小到大是1 2 3 是第 1 个1 3 2 是第 2 个2 1 3 是第 3 个2 3 1 是第 4 个3 1 2 是第 5 个3 2 1 是第 6 个所以当你输入 3 和 2 3 1程序应该输出 4。这里“字典序”的含义其实很简单就像查字典比较单词一样从第一个数字开始比较数字小的排在前面如果第一个数字相同再比较第二个数字以此类推。题目本质就是给你一个目标状态求它在“全排列集合中的排名”。1.2 为什么这道题是学 DFS 的绝佳载体很多入门帖喜欢拿全排列来教 DFS不是没有道理的。一个长度为 n 的排列本质上是一个“逐位填数字”的过程先填第一位有 n 种选择确定第一位后第二位有 n-1 种选择接着第三位有 n-2 种选择……这个过程天然形成一棵递归树。而 DFS 做的事就是在这棵树上“一条路走到黑走不通就退回来走另一条”。它的递归调用栈恰好和“填第几位”这件事一一对应。更妙的是如果你在递归里用 for 循环从小到大去尝试候选数字DFS 生成的排列顺序天然就是字典序。也就是说只要你按照 DFS 的方式去枚举排列你的枚举顺序就已经是“从小到大”一点都不用额外排序。很多第一次写这题的人会说“为什么我的 DFS 列出来的顺序刚好是字典序”答案就在这个 for 循环的顺序里。所以“排列序数”这道题表面上求的是排名实际上练的是递归状态怎么设计、回溯操作怎么正确撤销、计数时机怎么不犯糊涂。这三件事几乎是所有 DFS 题目通用的底层能力。2. 从一棵递归树看懂 DFS 的状态设计2.1 路径、选择列表、结束条件三要素我用过很多方法去理解 DFS最后发现最不容易错的框架是“路径 选择列表 结束条件”三件套路径已经选好的数字序列也就是当前已经填好的部分排列。选择列表还有哪些数字可以填。代码里不直接维护一个动态列表而是用一个布尔数组 used 来标记“某个数字是否已经被选过”在 for 循环里逐个判断。结束条件路径的长度已经达到 n说明一个完整排列构建完成此时就可以对这个排列进行处理。这个框架最大的好处是你在写递归函数之前先问自己三个问题当前状态是什么下一步有哪些选择什么时候算到底只要把这三个问题想清楚代码的骨架基本就出来了。以 n4 为例递归树的前两层会长这样第1位可选1, 2, 3, 4 选定1后第2位可选2, 3, 4 选定1,2后第3位可选3, 4 选定1,2,3后第4位只能选4如果画出整棵树每个叶子节点就是一个完整排列。从根到叶子的每一条路径就是一个排列的生成过程。2.2 回溯操作为什么要成对出现这是所有 DFS 新手第一次写这题时最容易翻车的地方。我见过最多的一种错误代码长这样for i in range(1, n 1): if not used[i]: used[i] True path.append(i) dfs() # 忘了取消标记 # path.pop() 也忘了看起来只少了两个操作但程序会出大问题当你从一个分支退出来准备尝试下一个数字时上一个分支已经用过的数字仍然被标记为“已被占用”这就导致很多合法的选择被跳过最终生成的排列数量远小于 n!。你可以把回溯理解成“借书”你从书架上拿下一本书必须在放回之后才能去拿另一本。DFS 里的 used[i] True 相当于拿走used[i] False 相当于放回path.append(i) 相当于把这本书放进你的书包path.pop() 相当于把书从书包里拿出来。借了不还下次就永远借不到那本书。所以记住一条铁律递归前的状态修改必须在递归后对称撤销。写成代码就是used[i] True path.append(i) dfs() used[i] False path.pop()这两组操作之间的距离只有一行 dfs()但它们必须严格成对。这不是风格问题是正确性问题。在很多版本的代码里你还会看到先 path.pop() 再 used[i] False顺序无所谓但一定要两个都执行。2.3 DFS 为什么天然输出字典序我在 1.2 里提过这个问题但值得再深入一点。假设 n3我们从第一层开始 for 循环先尝试 1然后递归去构建 1 开头的所有排列1 2 3、1 3 2全部枚举完接着回到第一层的 for 循环尝试 2再构建 2 开头的所有排列。由于 for 循环从小到大所以第一层的顺序是 1、2、3第二层在固定的第一位数下也是从小到大去试没用过的数字第三层同理。于是整个枚举顺序就是先把所有 1 开头的排完再排所有 2 开头的再排所有 3 开头的。这不就是字典序吗如果你把递归树画出来从左到右读所有叶子节点就是字典序全排列。这个性质在“排列序数”这题里特别有用因为你知道枚举顺序就是字典序所以只要在枚举到目标排列时输出当前计数结果一定是正确的排名。这也是为什么这题适合直接用 DFS 暴力枚举而不是先算数学公式。3. 完整代码实现与逐步排错3.1 Python 版实现下面是我推荐初学者参考的写法。我特意把计数器也放在递归函数外面用列表包了一层原因稍后解释。def permutation_order(n, target): used [False] * (n 1) # used[i] 表示数字 i 是否已经被选过 path [] # 当前构建中的排列 count [0] # 已生成的完整排列数量 def dfs(): # 结束条件路径长度达到 n说明一个排列构造完毕 if len(path) n: count[0] 1 if path target: return count[0] return None # 尝试所有可选数字从小到大 for i in range(1, n 1): if not used[i]: used[i] True path.append(i) res dfs() if res is not None: return res path.pop() used[i] False return None ans dfs() return ans if ans is not None else -1 n 3 target [2, 3, 1] print(permutation_order(n, target)) # 输出 4有几个细节我想重点说。第一count 为什么用[0]而不是一个整数变量因为 Python 里整数是不可变类型你在嵌套函数里直接写count 1时Python 会把 count 当成一个新的局部变量导致 UnboundLocalError。解决办法有三种用列表包一层、在嵌套函数里声明 nonlocal、或者把 count 当作参数传来传去。列表包一层是最直观的写法对新手也友好。第二dfs() 返回值的设计。找到目标排列时把 count[0] 的值一层一层返回上去没找到就返回 None。这样一旦找到答案递归调用会立刻逐层返回而不会继续生成后面的无用排列。虽然暴力枚举全体排列本身是 O(n!)但能在找到目标后提前终止对中等规模的 n 也能节省不少时间。第三其实也可以把 count 设计成“全局变量 内部函数用 nonlocal”但我个人觉得练习阶段先不要引入 nonlocal 概念等基础扎实了再优化写法。条条大路通罗马先选择最容易理解的那条。3.2 计数器到底放在哪里才准确这一小节可以说是本篇文章最实在的干货之一。我见过至少三种计数错误版本逐一说明。错误版本一在 for 循环内部就 count[0] 1。这样一来每尝试一个数字都计数而不是每完成一个排列才计数。你得到的数字会远远大于 n!而且毫无意义。错误版本二在 len(path) n 之后先打印 path 再计数。这个功能上没错但如果你在判断 target 之前就把 count 加了那第一个排列就会变成 2 号整体偏移一位。很多人的代码结果总是比标准答案大 1 或者小 1往往就是这种边界问题。错误版本三把结束条件写成if len(path) n: count[0] 1然后在主函数里又额外调用一次 dfs导致重复计数。这种情况通常出现在你同时写了循环和递归入口的时候简单说递归的入口只需要调用一次不要在外面套一层 for 循环。正确的计数时机只有一个在“路径长度达到 n”的这个分支里且只能在判断目标排列之前或者之后立刻计数。先计数还是先判断答案是一样的因为每个完整排列都会被计数一次。代码里我写成先 count[0] 1再判断是否等于 target逻辑上没有任何问题。3.3 手动走一遍 n3 的完整流程纸上得来终觉浅我建议每个初学者都在草稿纸上手动模拟一遍你会发现 DFS 其实比想象中来得简单。下面以 target [2, 3, 1] 为例。第一次调用 dfs()path 为空。进入 for 循环i1used[1]Truepath[1]。然后递归。当前 path[1]len(path)1≠3。for 循环从 1 开始1 已被用过所以 i2used[2]Truepath[1,2]。再次递归。当前 path[1,2]for 循环从 1 开始1、2 都被用过所以 i3used[3]Truepath[1,2,3]。再次递归。len(path)3count[0] 变成 1path 不等于 [2,3,1]返回 None。一层层退回来注意每退回一层都要把 used 和 path 的修改撤销。当 path[1] 时for 循环继续i3 可用used[3]Truepath[1,3]。递归后填 2得到 [1,3,2]。count[0] 变成 2不匹配返回 None。继续回溯到 path[]第一层 for 循环 i1 的分支结束。接着 i2used[2]Truepath[2]。往下依次得到[2,1,3]count[0]3[2,3,1]count[0]4匹配 target返回 4整个流程用表格看就是枚举顺序排列序号是否匹配11 2 31否21 3 22否32 1 33否42 3 14是你发现没有DFS 每次往深处走时都是“填一位、选一个没用过的数字”每到一个叶子节点就是一个排列。手动模拟一遍之后“递归树”就不再是一个抽象概念而是你能实实在在画出来的东西。4. 优化与验证引入康托展开做“参考答案”4.1 康托展开的原理解读写完了 DFS 暴力枚举版我再推荐你掌握一个用来验证结果的方法——康托展开。它是专门计算排列序数的数学方法时间复杂度可以做到 O(n^2) 甚至 O(n log n)比枚举 n! 个排列快得多。康托展开的核心公式是这样的X a1*(n-1)! a2*(n-2)! ... a(n-1)*1! an*0!其中 ai 表示“第 i 位数字后面有多少个比它更小的数字”。X 是从 0 开始的排名最终结果要加 1。拿 n3排列 [2, 3, 1] 来算第一位是 2它后面比 2 小的数字有 1共 1 个所以 a11对应贡献 1 * 2! 2。第二位是 3它后面比 3 小的数字只有 1共 1 个所以 a21对应贡献 1 * 1! 1。第三位是 1它后面没有数字a30对应贡献 0 * 0! 0。X 2 1 0 3最终排名是 X1 4。和 DFS 枚举的结果完全一致。康托展开的原理其实也很好理解它统计的是“在我这个排列之前已经有多少个排列被跳过了”。第一位是 2说明所有以 1 开头的排列都被跳过了数量是 2! 个也就是 2第二位是 3在前缀为 2 的前提下说明前缀是 2 1 的所有排列也被跳过了数量是 1! 个也就是 1。加起来正好是 3 个先于它的排列所以它是第 4 个。4.2 DFS 暴力枚举和康托展开怎么配合比赛或者做题时如果 n 很小比如 n≤9DFS 全排列完全够用代码写起来也直观。如果 n 到了 12n! 479001600枚举所有排列基本属于“不可接受”的复杂度这时候就应该用康托展开。但我不建议新手一上来就背康托展开公式。理由很简单公式很容易记混而一旦你先把 DFS 跑通了你能亲手看到“枚举顺序就是字典序”这件事再去看康托展开的推导就会瞬间明白每一个 a[i] 都在统计什么。纸上得来终觉浅亲自枚举一遍全排列比你背十遍公式都有用。如果你自己写了康托展开我强烈建议你用 DFS 的答案去验证。我平时就这么干先跑一遍暴力 DFS 得到结果再用康托展开计算一遍两个结果不一致就去看代码逻辑。对于 n 比较小的情况两者应该严格相等。这种“双实现互相验证”的学习方式可以帮你很快定位到自己对哪个环节理解有偏差。5. 常见问题与踩坑记录5.1 DFS 新手最容易踩的四个坑写排列序数这道题时我总结过几个高频错误。每一个都是我亲眼见过、或者自己曾经踩进去过的。第一个坑忘记回溯。前面提过这是最经典的问题。症状是输出的排列数量不对而且会有大量排列重复或者缺失。解决办法就是把“递归前修改状态、递归后撤销状态”当成肌肉记忆每次提交前检查 used 和 path 的修改是否成对。第二个坑计数时机不对。症状是输出结果总是差 1或者大得离谱。记住只有 len(path) n 时才代表生成了一个完整排列这时候才计数。不要在前面任何一层去 count[0] 1。第三个坑递归没有出口或者出口顺序不对。比如有些人在 dfs() 开头忘记判断结束条件结果递归无限深入直到 Python 抛 RuntimeError。也有些人在 len(path) n 之后又去尝试 for 循环导致索引越界。结束条件必须是 dfs() 里的第一个检查逻辑。第四个坑尝试列表的顺序被破坏。如果 n 不是从 1 到 n 而是从 0 到 n-1for 循环范围就要相应调整如果你让目标排列 target 和枚举排列 path 的数据类型不一致比如一个是列表一个是字符串比较时就永远为 False。这些细节看起来很小但在实际调错时能让人抓狂半天。5.2 复杂度边界与非递归实现思路暴力 DFS 的时间复杂度是 O(n!)空间复杂度是 O(n)递归栈深度 path 长度。我在本地跑过n9 的时候非常轻松n10 也还行n11 开始就明显感觉到卡顿。所以如果题目给出的 n 超过 11你基本可以确定出题人的意图是考数学方法而不是暴力枚举。除了康托展开还有一种常见的非递归实现方式是直接用栈模拟 DFS。思路是手动维护一个栈栈里保存当前状态当前路径和已尝试到哪个数字。这种方式不需要系统递归可以避开 Python 默认的 1000 层递归限制但代码可读性会差一些。练习阶段我建议先把递归版吃透再考虑用栈去模拟因为递归版更贴近“一棵树向下探索”的直觉。还有一个容易忽略的点Python 的 sys.setrecursionlimit 可以调高递归深度限制但这只是让程序不会立刻崩溃并不代表 n100 时枚举全排列是可行的。复杂度是数学上的硬限制递归深度是运行环境的限制两者不是一回事。5.3 从一道题的 AC 到学会一类题最后想聊点实际的体会。如果你今天第一次写这题我建议你不只要 AC还要尝试做这几件事把 n4 的递归树完整画出来然后用程序输出验证你的树是否完整。2. 把代码里的 for 循环改成从 n 到 1 反向遍历看看输出顺序变成什么样思考为什么。3. 在 dfs() 入口打印当前 path观察打印顺序和字典序之间的关系。4. 尝试用 target 提前剪枝比如当前 path 的前缀已经和目标排列完全不一致且不可能相等时提前 return。做完这四件事你对 DFS 的理解会从“背模板”变成“懂机制”。以后再遇到八皇后、子集、组合、迷宫寻路这些题你会发现它们都是同一棵递归树上的不同问题。我自己学下来最大的感受就是DFS 本身不复杂复杂的是你想不清状态是什么、边界在哪里。而排列序数这道题正好用最小的复杂度把这些问题全部暴露出来。多手推几遍比刷十道类似题都管用。