企业官网建设流程全解析

这道题我印象挺深的，是我入门DFS时手写过的第一道“有点意思”的题：给定一个由 1~n 组成的排列，让你算出它在所有排列里按字典序排第几个。比如 n=3，排列 2 3 1 是第 4 个。题目名称直接就叫“深度优先搜索(DFS)练习1——排列序数”，一看就知道是拿来练 DFS 的。

如果你刚学 DFS，经常遇到“知道要递归、也背过模板，但一写就乱”的情况，那这篇就是你的参考。我会从问题拆解、状态设计、代码实现一路讲到调试心得和康托展开验证，最后还会列一些新手必踩的坑。整个过程我会带着实际代码和手推过程走一遍，而不是只讲概念。

1. 先搞清楚我们在练什么：排列序数问题

1.1 题目到底在问什么

题目通常会这样描述：输入一个正整数 n，然后是 1 到 n 的一个排列（每个数字恰好出现一次），要求输出这个排列在 1~n 所有全排列中按字典序从小到大排序后的位置。位置从 1 开始计数。

举个例子，n=3，所有排列按字典序从小到大是：

• 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，说明一个完整排列构建完成，此时就可以对这个排列进行处理。

这个框架最大的好处是，你在写递归函数之前先问自己三个问题：当前状态是什么？下一步有哪些选择？什么时候算到底？只要把这三个问题想清楚，代码的骨架基本就出来了。

以 n=4 为例，递归树的前两层会长这样：

第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 里提过这个问题，但值得再深入一点。假设 n=3，我们从第一层开始 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 手动走一遍 n=3 的完整流程

纸上得来终觉浅，我建议每个初学者都在草稿纸上手动模拟一遍，你会发现 DFS 其实比想象中来得简单。下面以 target = [2, 3, 1] 为例。

第一次调用 dfs()，path 为空。进入 for 循环，i=1，used[1]=True，path=[1]。然后递归。

当前 path=[1]，len(path)=1≠3。for 循环从 1 开始，1 已被用过，所以 i=2，used[2]=True，path=[1,2]。再次递归。

当前 path=[1,2]，for 循环从 1 开始，1、2 都被用过，所以 i=3，used[3]=True，path=[1,2,3]。再次递归。

len(path)=3，count[0] 变成 1，path 不等于 [2,3,1]，返回 None。

一层层退回来，注意每退回一层，都要把 used 和 path 的修改撤销。当 path=[1] 时，for 循环继续，i=3 可用，used[3]=True，path=[1,3]。递归后填 2，得到 [1,3,2]。count[0] 变成 2，不匹配，返回 None。

继续回溯到 path=[]，第一层 for 循环 i=1 的分支结束。接着 i=2，used[2]=True，path=[2]。往下依次得到：

• [2,1,3]，count[0]=3
• [2,3,1]，count[0]=4，匹配 target，返回 4

整个流程用表格看就是：

你发现没有，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。

拿 n=3，排列 [2, 3, 1] 来算：

• 第一位是 2，它后面比 2 小的数字有 1，共 1 个，所以 a1=1，对应贡献 1 * 2! = 2。
• 第二位是 3，它后面比 3 小的数字只有 1，共 1 个，所以 a2=1，对应贡献 1 * 1! = 1。
• 第三位是 1，它后面没有数字，a3=0，对应贡献 0 * 0! = 0。

X = 2 + 1 + 0 = 3，最终排名是 X+1 = 4。和 DFS 枚举的结果完全一致。

康托展开的原理其实也很好理解：它统计的是“在我这个排列之前，已经有多少个排列被跳过了”。第一位是 2，说明所有以 1 开头的排列都被跳过了，数量是 2! 个，也就是 2；第二位是 3（在前缀为 2 的前提下），说明前缀是 2 1 的所有排列也被跳过了，数量是 1! 个，也就是 1。加起来正好是 3 个先于它的排列，所以它是第 4 个。

4.2 DFS 暴力枚举和康托展开怎么配合

比赛或者做题时，如果 n 很小（比如 n≤9），DFS 全排列完全够用，代码写起来也直观。如果 n 到了 12，n! = 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-1，for 循环范围就要相应调整；如果你让目标排列 target 和枚举排列 path 的数据类型不一致（比如一个是列表，一个是字符串），比较时就永远为 False。这些细节看起来很小，但在实际调错时能让人抓狂半天。

5.2 复杂度边界与非递归实现思路

暴力 DFS 的时间复杂度是 O(n!)，空间复杂度是 O(n)（递归栈深度 + path 长度）。我在本地跑过，n=9 的时候非常轻松，n=10 也还行，n=11 开始就明显感觉到卡顿。所以如果题目给出的 n 超过 11，你基本可以确定出题人的意图是考数学方法而不是暴力枚举。

除了康托展开，还有一种常见的非递归实现方式是直接用栈模拟 DFS。思路是手动维护一个栈，栈里保存当前状态（当前路径和已尝试到哪个数字）。这种方式不需要系统递归，可以避开 Python 默认的 1000 层递归限制，但代码可读性会差一些。练习阶段我建议先把递归版吃透，再考虑用栈去模拟，因为递归版更贴近“一棵树向下探索”的直觉。

还有一个容易忽略的点：Python 的 sys.setrecursionlimit 可以调高递归深度限制，但这只是让程序不会立刻崩溃，并不代表 n=100 时枚举全排列是可行的。复杂度是数学上的硬限制，递归深度是运行环境的限制，两者不是一回事。

5.3 从一道题的 AC 到学会一类题

最后想聊点实际的体会。如果你今天第一次写这题，我建议你不只要 AC，还要尝试做这几件事：

把 n=4 的递归树完整画出来，然后用程序输出验证你的树是否完整。2. 把代码里的 for 循环改成从 n 到 1 反向遍历，看看输出顺序变成什么样，思考为什么。3. 在 dfs() 入口打印当前 path，观察打印顺序和字典序之间的关系。4. 尝试用 target 提前剪枝，比如当前 path 的前缀已经和目标排列完全不一致且不可能相等时，提前 return。

做完这四件事，你对 DFS 的理解会从“背模板”变成“懂机制”。以后再遇到八皇后、子集、组合、迷宫寻路这些题，你会发现它们都是同一棵递归树上的不同问题。我自己学下来最大的感受就是：DFS 本身不复杂，复杂的是你想不清状态是什么、边界在哪里。而排列序数这道题，正好用最小的复杂度把这些问题全部暴露出来。多手推几遍，比刷十道类似题都管用。