备案号:蜀ICP备2026035467号-3| www.xservx.com

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 较大时,暴力生成可能导致内存溢出或超时。

⚡ 关键提示:全排列是有序的!{a,b} 与 {b,a} 是两个不同排列;而组合(combination)是无序的,{a,b} 与 {b,a} 视为同一组合。

算法原理与实现方法详解

1. 递归回溯法(深度优先搜索)

递归回溯是理解全排列最直观的方法:固定当前位置的元素,递归处理剩余位置。核心思想是「选择-递归-撤销选择」的三步模板。

算法流程

  1. 初始化空路径 path 和访问标记 visited 数组(或集合)
  2. 当 path 长度等于原数组长度时,保存当前排列
  3. 遍历每个元素:若未被访问,则将其加入 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题)。核心步骤如下:

  1. 从右向左找出第一个 升序对 (i, i+1),即 nums[i] < nums[i+1]
  2. 若不存在升序对,说明已是最大排列,反转整个数组
  3. 在 i+1 到末尾中,从右向左找出第一个大于 nums[i] 的元素 j
  4. 交换 nums[i] 和 nums[j]
  5. 反转 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
⚡ 字典序法无需额外空间,空间复杂度为 O(1)(除结果存储),但每次生成下一个排列需 O(n) 时间,总时间仍为 O(n × n!)。

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
❗ Heap’s Algorithm 会 修改原数组!调用前请备份或使用副本。

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
❗ 字符串切片会创建新对象,递归深度大时效率低。建议转为列表操作或使用 itertools。

示例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 AlgorithmO(n!)O(n)否是交换次数最少场景
itertools.permutationsO(n × n!)O(r)(r为选取长度)是否工程首选,大n推荐

关键分析

  • 时间下界:必须生成 n! 个排列,每个排列长度 n,故下界为 Ω(n × n!),任何算法无法突破。
  • 空间瓶颈:递归法栈深度为 n;迭代法(如字典序)仅需常量额外空间。
  • 实际耗时:n=12 时,12! = 4.79×10⁸,单机生成约需数秒;n=15 时超 10¹²,不现实。
⚡ 实测数据(i7-12700H):n=10 时,itertools.permutations 生成 3628800 项约需 2.1 秒;n=11 需 23 秒;n=12 超 4 分钟。

性能优化技巧与实战调优

技巧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
⚠️ Cython 需额外编译步骤,开发复杂度上升。仅推荐在算法核心瓶颈时使用。

常见误区与边界问题排查

Q1:为什么递归版在 n>10 时崩溃? ▼

A:Python 默认递归深度限制为 1000(sys.getrecursionlimit())。全排列递归深度为 n,当 n≥1000 会抛出 RecursionError。解决方案:

  • 改用迭代法(如字典序、itertools)
  • 用 sys.setrecursionlimit() 提高限制(不推荐,易导致栈溢出)
Q2:去重时为何用 'not used[i-1]' 而非 'used[i-1]'? ▼

A:以 [1,1,2] 为例,排序后为 [1,1,2]。当处理第一个 1 时,第二个 1 尚未被访问(used[1]=False),跳过它会导致后续排列缺失。正确逻辑是:若前一相同元素刚被回溯(used[i-1]=False),说明已生成过以该元素开头的分支,需跳过当前相同元素避免重复。

Q3:itertools.permutations 返回元组,如何转列表? ▼

A:用列表推导式:[list(p) for p in permutations([1,2,3])];或直接消费:list(map(list, permutations([1,2,3])))

Q4:如何生成指定长度 r 的排列(如 P(5,3))? ▼

A:itertools.permutations(nums, r=3) 直接支持;自定义时需在递归中判断 path 长度是否达到 r 即可保存。

高频面试题真题解析

题目1:LeetCode #46 全排列(中等)

给定一个不含重复数字的数组 nums,返回其所有可能的全排列。

💡 考察点:递归回溯模板掌握、列表深拷贝、边界处理

题目2:LeetCode #47 全排列 II(中等)

给定一个可包含重复数字的序列 nums,按任意顺序返回所有不重复的全排列。

⚠️ 陷阱:去重条件错误(如用 used[i-1])、未排序导致跳过错误

题目3:字符串全排列(华为/腾讯面试题)

输入字符串 "aab",输出所有不重复排列:["aab","aba","baa"]

💡 关键:字符串转列表去重;或直接用 set 去重(但效率低)

题目4:时间复杂度追问

Q:全排列算法的时间复杂度能否优化到 O(n!)?

A:不能!因为输出大小本身就是 Θ(n!),任何算法必须至少输出 n! 项,下界为 Ω(n × n!)。O(n!) 是错误表述。

问答社区精选

Q:如何快速验证全排列结果正确性?

A:三步校验法:

  1. 数量校验:结果数是否为 n!(或 r! × C(n,r))
  2. 元素校验:每个排列是否包含原集合所有元素(无遗漏/多余)
  3. 唯一性校验:结果列表转为 set 后长度是否等于原长度(去重后)

Q:全排列与哈密顿路径有何关联?

A:在完全图中,哈密顿路径的数量等于 n! / 2(无向图)。全排列可视为有向完全图的哈密顿路径枚举。

Q:能否用动态规划求全排列?

A:不能直接用。动态规划适用于子问题重叠,但全排列的子问题(前k个元素排列)与原问题结构不同,无法复用结果。回溯/迭代才是标准解法。