Python全排列算法|递归·字典序·回溯·源码解析·实战应用
全排列是组合数学中的基础问题,指给定一个包含 互异元素 的集合,求出该集合所有可能的排列顺序。在计算机科学中,全排列算法广泛应用于密码破解、路径规划、生物信息学序列比对、组合优化、游戏AI状态空间生成等场景。Python因其简洁语法与强大标准库,成为实现全排列算法的首选语言之一。
本文系统讲解Python中实现全排列的四大核心方法:递归回溯法、字典序生成法、itertools.permutations内置函数及堆算法(Heap’s Algorithm),并深入对比其时间复杂度、空间复杂度、适用场景与边界条件。同时结合LeetCode高频真题、常见面试陷阱、性能调优技巧与实际工程案例,帮助开发者从原理到实践全面掌握该算法体系。
特别说明:全排列的前提是输入集合中元素 互不相同。若存在重复元素,需额外去重逻辑(如排序+跳过重复值),否则将产生重复排列。此问题在LeetCode第47题「全排列 II」中重点考察,本文也将深入剖析其解法差异与陷阱规避。
📌 什么是全排列?数学定义与直观理解
设集合 S = {a₁, a₂, ..., aₙ},其中所有元素互异,则其全排列(permutation)是 S 中所有元素的有序排列的集合,总数为 n!(n阶乘)。例如:
- 当 n=1:S={a} → 排列数=1! = 1 → [a]
- 当 n=2:S={a,b} → 排列数=2! = 2 → [a,b]、[b,a]
- 当 n=3:S={a,b,c} → 排列数=6 → [a,b,c]、[a,c,b]、[b,a,c]、[b,c,a]、[c,a,b]、[c,b,a]
排列总数增长极快:5! = 120,10! = 3,628,800,15! ≈ 1.3×10¹²。因此全排列算法必须兼顾正确性与效率,尤其在 n 较大时,暴力生成可能导致内存溢出或超时。
算法原理与实现方法详解
1. 递归回溯法(深度优先搜索)
递归回溯是理解全排列最直观的方法:固定当前位置的元素,递归处理剩余位置。核心思想是「选择-递归-撤销选择」的三步模板。
算法流程
- 初始化空路径
path和访问标记visited数组(或集合) - 当
path长度等于原数组长度时,保存当前排列 - 遍历每个元素:若未被访问,则将其加入
path),标记为已访问,递归;递归返回后撤销选择
代码实现(Python)
def permute_recursive(nums):
res = []
path = []
visited = [False] * len(nums)
def backtrack():
if len(path) == len(nums):
res.append(path[:]) # 深拷贝
return
for i in range(len(nums)):
if not visited[i]:
path.append(nums[i])
visited[i] = True
backtrack()
path.pop()
visited[i] = False
backtrack()
return res
path[:] 或 list(path) 进行深拷贝!否则所有元素引用同一列表对象,最终结果全为空或重复。
2. 字典序算法(Next Permutation)
字典序法按字典序从小到大生成所有排列,适用于需要有序输出的场景(如LeetCode第31题)。核心步骤如下:
- 从右向左找出第一个 升序对 (i, i+1),即 nums[i] < nums[i+1]
- 若不存在升序对,说明已是最大排列,反转整个数组
- 在 i+1 到末尾中,从右向左找出第一个大于 nums[i] 的元素 j
- 交换 nums[i] 和 nums[j]
- 反转 i+1 到末尾的子数组(使其变为最小字典序)
生成全排列的字典序法流程
def permute_lexicographic(nums):
nums = sorted(nums) # 先排序保证从最小字典序开始
res = []
while True:
res.append(nums[:])
# Step 1: find first i where nums[i] < nums[i+1]
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
if i < 0:
break # 已是最大排列
# Step 2: find j > i where nums[j] > nums[i]
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
# Step 3: swap nums[i], nums[j]
nums[i], nums[j] = nums[j], nums[i]
# Step 4: reverse i+1 to end
nums[i+1:] = reversed(nums[i+1:])
return res
3. Heap’s Algorithm(堆算法)
Heap’s Algorithm 是一种高效生成全排列的递归算法,时间复杂度 O(n!),但交换次数最少(仅 n! 次),适合嵌入式或资源受限环境。
核心思想:固定最后一个元素,递归生成前 n-1 个元素的排列;当 n 为奇数时交换首尾,n 为偶数时交换第 i 个与末尾。
代码实现
def heap_permute(nums):
res = []
a = nums[:]
def generate(k):
if k == 1:
res.append(a[:])
return
generate(k - 1)
for i in range(k - 1):
if k % 2 == 0:
a[i], a[k-1] = a[k-1], a[i]
else:
a[0], a[k-1] = a[k-1], a[0]
generate(k - 1)
generate(len(a))
return res
4. itertools.permutations 源码解析
Python内置模块 itertools 提供了高效全排列生成器:itertools.permutations(iterable, r=None)。其源码采用迭代方式,避免递归栈溢出,适合大 n 场景。
核心逻辑伪代码(简化版)
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = list(range(n))
cycles = list(range(n, n-r, -1))
yield tuple(pool[i] for i in indices[:r])
while True:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
itertools.permutations 是生成器(generator),惰性求值,内存友好。返回的是迭代器,需用 list() 或循环消费。
经典示例与变体解析
示例1:基础全排列(无重复元素)
输入:[1, 2, 3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
使用 itertools.permutations(推荐)
from itertools import permutations
list(permutations([1,2,3]))
# → [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
示例2:含重复元素的全排列(LeetCode #47)
输入:[1,1,2] 输出:[[1,1,2],[1,2,1],[2,1,1]](去重)
常见错误:直接用递归法会产生重复排列!如 [1(1),1(2),2] 与 [1(2),1(1),2] 实际相同。
正确去重方法(排序+跳过)
def permute_unique(nums):
nums.sort() # 先排序
res = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# 关键:跳过重复:当前与前一相同,且前一未被使用(说明刚回溯过)
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
backtrack(path + [nums[i]])
used[i] = False
backtrack([])
return res
not used[i-1] 是关键!若写成 used[i-1] 会跳过所有后续排列。
示例3:字符串全排列
输入:"abc" 输出:["abc","acb","bac","bca","cab","cba"]
递归实现(字符串切片)
def permute_string(s):
if len(s) <= 1:
return [s]
res = []
for i, ch in enumerate(s):
for perm in permute_string(s[:i] + s[i+1:]):
res.append(ch + perm)
return res
示例4:生成器版本(内存优化)
当 n 较大时(如 n=10),全排列共 3628800 项,若一次性生成列表会内存溢出。使用生成器惰性求值更安全。
递归生成器实现
def permute_gen(nums):
if not nums:
yield []
return
for i, ch in enumerate(nums):
for rest in permute_gen(nums[:i] + nums[i+1:]):
yield [ch] + rest
调用方式:for p in permute_gen([1,2,3]): print(p) —— 逐个处理,不占用大量内存。
时间复杂度与空间复杂度深度对比
| 算法 | 时间复杂度 | 空间复杂度 | 是否有序 | 是否递归 | 适用场景 |
|---|---|---|---|---|---|
| 递归回溯 | O(n × n!) | O(n)(递归栈) | 否 | 是 | 教学、小规模数据 |
| 字典序法 | O(n × n!) | O(1) | 是 | 否 | 需有序输出、无额外空间 |
| Heap’s Algorithm | O(n!) | O(n) | 否 | 是 | 交换次数最少场景 |
| itertools.permutations | O(n × n!) | O(r)(r为选取长度) | 是 | 否 | 工程首选,大n推荐 |
关键分析
- 时间下界:必须生成 n! 个排列,每个排列长度 n,故下界为 Ω(n × n!),任何算法无法突破。
- 空间瓶颈:递归法栈深度为 n;迭代法(如字典序)仅需常量额外空间。
- 实际耗时:n=12 时,12! = 4.79×10⁸,单机生成约需数秒;n=15 时超 10¹²,不现实。
性能优化技巧与实战调优
技巧1:避免深拷贝开销
在递归回溯中,频繁的 path[:] = path.copy() 是性能瓶颈。优化方式:
- 使用原地修改 + 回溯撤销(如 Heap’s Algorithm)
- 用索引代替切片:传递 start/end 索引而非新列表
优化示例(索引版回溯)
def permute_optimized(nums):
res = []
def backtrack(start):
if start == len(nums):
res.append(nums[:]) # 只在保存时深拷贝
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
backtrack(0)
return res
技巧2:使用生成器惰性求值
对大规模数据,优先返回生成器而非列表:
生成器版 itertools 风格
def permute_generator(nums):
if not nums:
yield ()
return
for i, x in enumerate(nums):
for rest in permute_generator(nums[:i] + nums[i+1:]):
yield (x,) + rest
技巧3:结合 Cython 或 Numba 加速
对性能极致要求(如科学计算),可将核心循环用 Cython 编译:
Cython 优化片段(.pyx 文件)
def permute_cython(list nums):
cdef int n = len(nums)
cdef list res = []
cdef list path = [0]*n
cdef list used = [0]*n
def backtrack(int pos):
if pos == n:
res.append(path[:])
return
for int i in range(n):
if not used[i]:
path[pos] = nums[i]
used[i] = 1
backtrack(pos+1)
used[i] = 0
backtrack(0)
return res
常见误区与边界问题排查
A:Python 默认递归深度限制为 1000(sys.getrecursionlimit())。全排列递归深度为 n,当 n≥1000 会抛出 RecursionError。解决方案:
- 改用迭代法(如字典序、itertools)
- 用 sys.setrecursionlimit() 提高限制(不推荐,易导致栈溢出)
A:以 [1,1,2] 为例,排序后为 [1,1,2]。当处理第一个 1 时,第二个 1 尚未被访问(used[1]=False),跳过它会导致后续排列缺失。正确逻辑是:若前一相同元素刚被回溯(used[i-1]=False),说明已生成过以该元素开头的分支,需跳过当前相同元素避免重复。
A:用列表推导式:[list(p) for p in permutations([1,2,3])];或直接消费:list(map(list, permutations([1,2,3])))
A:itertools.permutations(nums, r=3) 直接支持;自定义时需在递归中判断 path 长度是否达到 r 即可保存。
高频面试题真题解析
题目1:LeetCode #46 全排列(中等)
给定一个不含重复数字的数组 nums,返回其所有可能的全排列。
题目2:LeetCode #47 全排列 II(中等)
给定一个可包含重复数字的序列 nums,按任意顺序返回所有不重复的全排列。
题目3:字符串全排列(华为/腾讯面试题)
输入字符串 "aab",输出所有不重复排列:["aab","aba","baa"]
题目4:时间复杂度追问
Q:全排列算法的时间复杂度能否优化到 O(n!)?
A:不能!因为输出大小本身就是 Θ(n!),任何算法必须至少输出 n! 项,下界为 Ω(n × n!)。O(n!) 是错误表述。
问答社区精选
Q:如何快速验证全排列结果正确性?
A:三步校验法:
- 数量校验:结果数是否为 n!(或 r! × C(n,r))
- 元素校验:每个排列是否包含原集合所有元素(无遗漏/多余)
- 唯一性校验:结果列表转为 set 后长度是否等于原长度(去重后)
Q:全排列与哈密顿路径有何关联?
A:在完全图中,哈密顿路径的数量等于 n! / 2(无向图)。全排列可视为有向完全图的哈密顿路径枚举。
Q:能否用动态规划求全排列?
A:不能直接用。动态规划适用于子问题重叠,但全排列的子问题(前k个元素排列)与原问题结构不同,无法复用结果。回溯/迭代才是标准解法。