Python中的排列组合调用内置函数、自写算法DFS实现但凡写过一阵子Python迟早会遇到排列组合这件事。不管是暴力枚举所有可能性、生成测试用例、还是刷LeetCode时碰到子集/全排列/组合总和最终都会落到同一个问题上怎么高效又不出错地把所有排列或组合列出来。我见过不少新手卡在这里要么死记硬背itertools的API要么一听DFS就头大觉得递归太抽象。其实这两条路并不对立内置函数用来快速落地DFS用来理解本质今天我把两条路线放在一起拆开讲顺便把我踩过的坑也一并倒出来。这篇文章适合谁刚学Python不久、想搞懂排列组合怎么写的小白以及刷题时对DFS模板总是似懂非懂的初学者。我会先用生活化的方式讲清楚“排列”和“组合”到底差在哪再讲内置函数怎么一行搞定最后手写DFS并逐步优化全程带上可直接复制的完整代码和运行结果你可以边看边敲。1. 内容整体设计与思路拆解1.1 为什么要同时讲内置函数和DFS这个话题最尴尬的地方在于用内置函数太简单简单到让人产生“我会了”的错觉而自己写DFS又太难难到让人怀疑人生。如果你只学内置函数确实能解决80%的日常需求但一旦遇到需要剪枝、去重、自定义状态追溯的场景比如八皇后、数独、排列组合的变种题内置函数就帮不上忙了你必须手写搜索逻辑。反过来如果只学DFS你会发现写出来的代码冗长且容易出错明明三行就能出结果非要写十几行递归效率太低。所以我的思路是双轨并行先讲内置函数让你在工程里能快速用起来再讲DFS让你理解底层到底发生了什么。两条线索交叉印证——当你看见DFS的递归树时你才能真正理解为什么permutations和combinations返回的结果数量差那么多当你用内置函数跑通一个场景后你也能反过来检验自己手写的DFS是否正确。这种对比学习的方式比孤立地背任何一个方案都有效。1.2 排列与组合的本质区别很多新手挂在嘴边的一句话是“排列组合不就是把元素选出来嘛有啥区别”区别可太大了。排列关心顺序组合不关心顺序。举个例子从[A, B, C]中选2个元素排列会得到AB和BA两个结果因为它们顺序不同是两种不同的情况组合则只会得到{A, B}一个结果因为无论先写A还是先写B选出来的集合都是同一个。这个“是否区分顺序”的差异直接影响结果数量和算法写法。排列数的公式是A(n, k) n! / (n-k)!组合数的公式是C(n, k) n! / (k! * (n-k)!)。对于同样从3个元素中选2个排列数是6组合数是3恰好差了一个k!即2!这就是因为组合把AB和BA合并成了一个。用生活类比来加深记忆排列就像设置密码123和321是两个完全不同的密码组合就像买水果你挑了一个苹果一个香蕉先拿苹果还是先拿香蕉篮子里最终都是这两样东西没有区别。搞懂了这个底层的“顺序敏感性”后面写不同代码时你就明白哪些环节需要多检查一步“是否用过”哪些环节反而要刻意跳过重复分支。2. itertools内置函数实战一行代码搞定排列组合2.1 permutations与combinations的API细节Python标准库itertools里的permutations和combinations是处理排列组合的首选工具因为它们是C语言实现的性能远超纯Python手写而且经过无数人校验结果绝对可靠。from itertools import permutations, combinations data [A, B, C] # 排列从data中取2个元素的所有排列 print(list(permutations(data, 2))) # 输出: [(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)] # 组合从data中取2个元素的所有组合 print(list(combinations(data, 2))) # 输出: [(A, B), (A, C), (B, C)]注意两个细节。第一这两个函数返回的都是迭代器而不是列表所以要用list()包一层才能真正看到结果。这样设计的好处是如果元素数量巨大比如permutations(range(10))会产生约362万个结果使用迭代器可以边遍历边处理不会一次性占满内存。第二如果不传第二个参数rpermutations默认取全排列也就是len(data)个元素参与排列而combinations必须显式传入r否则会报错因为“全组合”这个概念本身没有意义。还有一个容易忽略的点这两个函数都要求输入序列中的元素是可哈希的数字、字符串、元组都没问题而且它们会把每个元素视为独一无二的对象。如果序列里有重复元素比如[1, 1, 2]permutations会输出两个(1, 1, 2)——因为两个1在底层索引上是不同的。这个坑我在3.2节会专门讲。2.2 product与combinations_with_replacement可重复选择的场景除了标准的排列组合实际应用中还经常遇到“允许重复选择”的场景比如掷骰子三次的所有可能结果或者从颜色列表中允许同色重复地取3个元素。这时候需要的是product和combinations_with_replacement。from itertools import product, combinations_with_replacement # product笛卡尔积相当于有放回且区分顺序的排列 print(list(product([1, 2], repeat2))) # 输出: [(1, 1), (1, 2), (2, 1), (2, 2)] # combinations_with_replacement有放回但不区分顺序的组合 print(list(combinations_with_replacement([1, 2], 2))) # 输出: [(1, 1), (1, 2), (2, 2)]这里有个很容易搞混的点product([1, 2], repeat2)的结果为什么是4个而permutations([1, 2], 2)只有2个因为permutations是“无放回抽取”一旦抽过1下一个位置就不能再抽1了而product是“有放回抽取”每次都在全集[1, 2]里选所以(1, 1)和(2, 2)这种重复元素的结果会出现。简单记忆permutations和combinations对应“不重复取样”product和combinations_with_replacement对应“可重复取样”。实际工作中我经常用product来生成笛卡尔积形式的测试用例。比如接口测试有三个参数每个参数有几种取值这时候product一行就能把所有取值组合全部展开比套三层for循环清爽得多代码可读性也好很多。2.3 告别重复元素set去重的正确姿势与代价前面提到permutations和combinations会把每个元素当作独立个体即使值相同也一样。也就是说[1, 1, 2]的全排列会被输出两次(1, 1, 2)因为两个1在底层索引上是不同的。最直接的解决办法是外面套一层set()去重但这里有两个性能隐患。第一去重的前提是把迭代器整个转化为列表或集合这会瞬间消耗大量内存。比如permutations(range(10))生成约362万个元组每个元组10个元素光结果就要占几百MB内存再套一个set内存直接翻倍甚至更多。第二结果中的元组属于可变对象的兄弟——虽然元组本身不可变但如果是包含列表的复杂结构set去重就无法正常工作因为列表不可哈希程序会直接报错。所以我的建议是能不用set去重就不用优先考虑在算法层面去重也就是在第3节手写DFS时通过排序和剪枝的方式排除重复分支。如果只是小规模数据用set图省事完全可以接受但一旦数据量上来老老实实手写去重逻辑的收益会远大于那几行简单代码。3. 手写DFS实现从递归模板到剪枝优化3.1 基础DFS模板用状态标记避免重复选择内置函数虽然好用但理解它背后发生的事情对解决复杂问题至关重要。手写排列组合最常见、也最贴合直觉的算法就是DFS也就是深度优先搜索。它的核心思想可以理解为“一条道走到黑走不动了就回头”——用一棵递归树描述所有可能性每个节点代表一个“已经选择了部分元素”的状态。直接先看一个最基础的全排列实现def permutations_dfs(nums): result [] used [False] * len(nums) def backtrack(path): # 递归终止条件当前路径长度等于数组长度说明已经选完所有元素 if len(path) len(nums): result.append(path[:]) # 注意这里用path[:]复制一份否则后续回溯会修改已存入的结果 return for i in range(len(nums)): if used[i]: # 如果当前元素已经在路径中跳过 continue used[i] True path.append(nums[i]) backtrack(path) # 回溯撤销本次选择尝试其他分支 path.pop() used[i] False backtrack([]) return result print(permutations_dfs([1, 2, 3])) # 输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]重点拆解一下这段代码。used数组是“选没选过”的标记它保证了同一个元素不会被重复使用这是排列和组合的公共底线。path是当前已选元素的集合每层递归往path里加一个元素当path长度达到目标长度时就产生了一个完整结果。这里有一个非常多新手跳进去的坑存储结果时直接用result.append(path)而不是result.append(path[:])。因为path在后续回溯过程中会不断被pop()和append()修改如果直接存path的引用最终结果里所有元素都会变成一模一样的最终状态通常是空列表。path[:]是切片复制相当于拍了一张当前状态的快照这样存进去的东西才不会被后续操作污染。3.2 排列组合的DFS一个模板适配所有场景理解了基础模板后你会发现排列、组合、子集问题其实都是一个框架下的变体差别只在于三行代码。我总结了一个适配力极强的模板稍微改改就能解决一大类问题。def dfs(nums, start, path, result, k): if len(path) k: result.append(path[:]) return for i in range(start, len(nums)): path.append(nums[i]) dfs(nums, i 1, path, result, k) # 组合从i1开始避免选了前面的再选后面的造成重复 path.pop()上面这个dfs是组合的写法核心就一个字start。排列和组合在DFS中的唯一区别就是下一层递归的起始位置。如果从0开始每次都从所有元素里挑得到的是排列如果从当前下标1开始只能往后挑得到的是组合。再看一个组合的去重写法这也是面试手写题的高频考点def combination_without_dup(nums, k): nums.sort() # 排序是去重的前提 result [] def backtrack(start, path): if len(path) k: result.append(path[:]) return for i in range(start, len(nums)): if i start and nums[i] nums[i-1]: continue # 同一个位置跳过重复值避免产生相同组合 path.append(nums[i]) backtrack(i 1, path) path.pop() backtrack(0, []) return result print(combination_without_dup([1, 2, 1, 3], 2)) # 输出: [[1, 1], [1, 2], [1, 3], [2, 3]]这里的核心逻辑是先排序让相同的元素相邻然后在每一层递归中如果当前元素和前一个元素相同且前一个元素没被选择过就跳过它。这样做的本质是在同一个“选择位置”值相同的元素只允许第一个被选中后面的全部剪枝掉。注意必须用i start而不是i 0因为start是当前层的决策起点不是整个数组的起点——如果用i 0你会误杀每一层的第一个元素导致结果少好多。3.3 剪枝优化与复杂度分析DFS如果不加任何优化随着n增大复杂度会爆炸式增长。全排列的时间复杂度是O(n!)组合是O(C(n, k))这已经不是“优化一百倍”能解决的问题而是“根本不可能穷举”的问题。但合理的剪枝可以在数据量较大的场景下少走很多冤枉路。什么是剪枝看一个具体例子有一个候选数字数组[2, 3, 6, 7]和一个目标值7需要找到所有“和等于7”的组合每个数可以用多次。如果你不加剪枝递归会一路走到天荒地老路径长度无限增加但如果你在递归开头就加一行if sum(path) target: return那么一旦和已经超出目标值就立刻return不再往下探索。这就把无限递归硬生生截断成了有限递归。再比如3.2节的去重代码用if i start and nums[i] nums[i-1]: continue本质上也是一种剪枝——它剪掉了“必然产生重复结果”的树枝。剪枝的核心原则是在递归树的早期阶段如果能判断某条分支不可能产生有效结果就立刻终止它。这个“判断”越早剪枝效果越好。我个人的经验是写剪枝前先别急着优化先把不剪枝的暴力版本跑通再用小规模数据验证正确性最后才考虑加剪枝条件。因为剪枝逻辑写错很容易导致少结果而且在递归的深水区非常难调试。先用小数据跑通基准版本再逐个加剪枝条件每加一个就对比一次结果是否一致这样能精确定位是哪个剪枝条件写错了。4. 实战对比与性能考量4.1 内置函数与DFS的结果一致性验证写完了DFS第一件事不是急着优化而是验证它和内置函数结果是否一致。因为内置函数是标准库经过无数人测试正确性有保证拿它当测试基准再合适不过。from itertools import permutations, combinations def permutations_dfs(nums): result [] used [False] * len(nums) def backtrack(path): if len(path) len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) backtrack(path) path.pop() used[i] False backtrack([]) return result def combinations_dfs(nums, k): result [] def backtrack(start, path): if len(path) k: result.append(path[:]) return for i in range(start, len(nums)): path.append(nums[i]) backtrack(i 1, path) path.pop() backtrack(0, []) return result # 验证排列 nums [1, 2, 3] assert sorted(permutations_dfs(nums)) sorted(list(permutations(nums))) # 验证组合 assert sorted(combinations_dfs(nums, 2)) sorted(list(combinations(nums, 2))) print(验证通过)为什么要用sorted()包一层再比较因为DFS遍历顺序和内置函数的输出顺序未必一致直接比较列表会误报错误。排序后只要两个结果集合内容相同顺序不同也无所谓。这个验证习惯值得养成——每次手写算法后先用小规模数据跟标准库对比确认无误后再上大任务能帮你省下大量调试时间。4.2 性能测试什么时候该放弃手写说句大实话如果只是日常工程需求能用itertools就用itertools别自己造轮子。itertools是C语言实现的底层做了大量优化性能比纯Python手写DFS高一个数量级。我用timeit简单测试过从10个元素中取4个的组合itertools.combinations耗时在微秒级而纯Python DFS耗时在毫秒级差距大约一千倍。那为什么还要学DFS因为有些场景内置函数根本做不了。举个例子你需要生成一个全排列但要求相邻两个元素的差必须大于某个阈值这时候内置函数只能先全量生成再去过滤如果数据量大中间结果直接爆内存而DFS可以在递归过程中加剪枝条件只产出合格结果相当于“一边生成一边筛选”空间和时间上都省得多。再比如带权重的排列组合、条件约束类问题内置函数没有可扩展的接口你必须手写搜索。还有一个场景如果你想深入理解算法或者准备面试DFS是必考内容。面试官不会问你“itertools的permutations怎么用”而会问你“不用内置函数实现全排列”这时候不学会DFS就没法交差。我的建议很明确工程里默认用内置函数碰到定制化需求再切换到DFS学习过程中一定要手推一遍DFS理解递归树的展开过程。两者不是替代关系而是互补关系。5. 常见问题与排查技巧实录5.1 结果顺序不一致有读者问为什么我用DFS生成的全排列结果和itertools.permutations的输出顺序不一样这是正常现象因为DFS默认按输入顺序选择元素而itertools内部有自己固定的字典序生成逻辑。只要元素内容一致顺序不同不影响正确性。如果确实需要保持一致的顺序可以给DFS的递归循环加上排序或者对最终结果统一排序。但为了对齐顺序做额外排序往往得不偿失我建议除非有强需求比如要和某个历史结果做diff否则直接忽略顺序差异。5.2 结果数量不对或丢失DFS最常见的问题就是结果数量不对通常是少了一些组合。排查思路按以下顺序走第一检查终止条件。if len(path) k写成了会导致什么当path长度超过k时才记录就漏掉了刚好等于k的结果。第二检查递归下一层的起始位置。组合问题要写backtrack(i 1, ...)如果误写成backtrack(i, ...)结果里就会出现大量重复每个元素都被重复选取多次数量暴增反之如果该排列却写了start 1结果就少了。这一行是排列和组合的分水岭每次写完都默念一遍排列是每次都从0开始组合是从当前位置的下一个开始。第三检查存储结果时是否用了path[:]。这个我在3.1节已经强调过如果直接result.append(path)最终所有结果都会变成同一个最终状态看起来就是“结果数量对但每个结果都一样”这是新手最容易踩的隐形坑。5.3 去重逻辑失效或误杀使用排序剪枝去重时最常见的报错是结果被“误杀”。比如combination_without_dup这个函数里如果去重条件写成if nums[i] nums[i-1]且不加i start的判断那么每一层的第一个元素会被当作“重复元素”跳过导致大量结果丢失。原因在于i start保证的是“在同一层递归中如果当前元素和前一个元素值相同且前一个元素已经被这一层的循环考虑过”这时才能跳过。换句话说只有在同一层已经处理过一次相同值时才需要去重不同层之间的相同元素是合法的不能一刀切。5.4 性能问题定位如果DFS在数据量稍微大一点时卡得无法忍受优先检查有没有做剪枝。一个简单的调试技巧是在每层递归入口统计调用次数打印出来。你会发现很多无谓的递归调用都发生在“路径长度已经不可能达到目标”的分支上。比如生成组合时如果当前路径长度加上剩余可选元素数量都小于k那这层就不用再递归了可以直接return。这个优化叫“可行性剪枝”代码就一行if len(path) (len(nums) - start) k: return加了这一行组合问题的递归调用次数能减少一大截尤其是k接近n时效果极其明显。类似的剪枝思维在排列问题上也可以扩展只要你能找到一个“当前状态下一定不可能产生合法结果”的判据就能安全减枝。写在后面的一点体会我从大一学Python开始就跟排列组合打交道前前后后在不同项目里写过几十次全排列但真正理解DFS的优美之处反而是很多年后在刷题平台遇到一道“组合总和”的变种题死活想不出怎么剪枝灵光一闪画出递归树才突然通透。所有排列组合问题本质上都是在一棵递归树上做有选择的遍历内置函数帮你把遍历过程封装好了DFS则让你亲手控制每一步走向哪里、什么时候回头。这两种能力都不是靠看出来的你对着文中的代码跑十遍把每个path的变化过程打印出来观察比死记硬背十个模板都管用。最后留个小作业试着把3.1节的permutations_dfs改成支持“可重复排列”也就是每一步都能从所有元素中选对比一下它和product的结果是否一致跑通了你对排列组合的理解就又深了一层。