1. 引言
在算法学习中，全排列（Permutation）是一个经典问题，它要求生成一个序列所有可能的排列方式。例如，序列[1, 2, 3]的全排列包括[1,2,3]、[1,3,2]、[2,1,3]等共 6 种。解决这个问题有多种方法，其中回溯法（Backtracking）结合递归是一种直观且高效的实现方式。
本文将使用 Python 递归实现全排列生成算法，分析其核心思想、代码细节，并探讨其时间复杂度和应用场景。
2. 核心代码示例
下面是一个完整、可运行的 Python 代码示例，它使用回溯法递归地生成数字 1 到 N 的所有全排列。
#!/usr/bin/env python3""" 全排列生成器 使用回溯法递归生成 1 到 N 的所有排列 """defgenerate_permutations(N):""" 生成 1 到 N 的所有全排列并打印。 参数: N (int): 排列中元素的最大值（从1开始）。 """# used 列表用于标记数字 i 是否已在当前路径中使用used=[False]*(N+1)# 索引 0 未使用，方便从1开始# result 列表存储当前正在构建的一个排列result=[0]*Ndefbacktrack(level):""" 递归回溯函数。 参数: level (int): 当前正在填充 result 的位置（0-based）。 """# 遍历所有可能的数字（1 到 N）fornuminrange(1,N+1):# 如果当前数字尚未被使用ifnotused[num]:# 做出选择：将数字放入当前位置used[num]=Trueresult[level]=num# 递归：填充下一个位置backtrack(level+1)# 撤销选择（回溯）：将数字标记为未使用，以便尝试其他分支used[num]=False# 基线条件：当 level 等于 N 时，说明一个完整的排列已构建完成iflevel==N:# 打印当前生成的一个完整排列print(*result)# 使用 * 操作符展开列表，用空格分隔打印# 从第 0 层（第一个位置）开始递归backtrack(0)if__name__=="__main__":print("生成 1 到 3 的全排列：")generate_permutations(3)预期运行结果
运行上述代码，将在控制台输出数字 1, 2, 3 的所有全排列：
生成 1 到 3 的全排列： 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1代码要点说明：
used列表：记录每个数字在当前递归路径（正在构建的排列）中是否已被使用，避免重复。result列表：存储当前正在构建的一个排列。backtrack函数：核心递归函数。- 选择：在每一层，遍历所有数字，将未使用的数字放入当前位置。
- 递归：进入下一层填充下一个位置。
- 撤销（回溯）：在递归返回后，将当前数字标记为未使用，以便在同一层尝试其他数字，探索不同的排列分支。
- 基线条件：当
level == N时，表示一个完整的排列已生成，将其打印输出。
这个示例清晰地展示了递归与回溯如何协同工作，系统地探索所有可能的解空间，是理解更复杂回溯问题（如八皇后、数独）的绝佳起点。
