Python算法竞赛：排列组合核心用法

排列组合是算法竞赛、笔试面试的高频考点核心区别排列重顺序组合不重顺序。Python 自带标准库可快速解题搭配回溯算法能覆盖所有变形场景。本文结合洛谷B2164组合数、洛谷P1706全排列、LeetCode77组合3道经典题一站式搞定排列组合的内置函数用法与手写实现。一、组合数计算只求数量不枚举洛谷B2164题目核心给定n、k求C(n,k) mod 1e97从n个元素选k个的方案数顺序无关。数学公式C(n,k)n!/(k!*(n−k)!)Python 极简解法math.combPython 3.10 提供math.comb直接计算组合数搭配取模即可通过本题。frommathimportcomb MOD10**97n,mmap(int,input().split())# 直接计算组合数并取模anscomb(n,m)%MODprint(ans)样例输入5 3 →输出10手写组合数兼容低版本defcalc_comb(n,k):ifk0orkn:return0ifk0orkn:return1kmin(k,n-k)# 减小计算量res1foriinrange(1,k1):resres*(n-ki)//ireturnres MOD10**97n,mmap(int,input().split())print(calc_comb(n,m)%MOD)二、全排列生成有序枚举所有序列洛谷P1706题目核心按字典序输出1~n的全排列每个数字占5个字符宽度。核心概念排列元素顺序不同算不同结果用itertools.permutations生成。Python 标准库解法fromitertoolsimportpermutations nint(input())# 生成1~n的列表numslist(range(1,n1))# 生成全排列permspermutations(nums)# 按格式拼接每个数字占5位result[.join(f{num:5d}fornuminp)forpinperms]print(\n.join(result))样例输入3 → 输出按要求对齐的6行全排列。回溯手写全排列竞赛必备模板nint(input())res[]used[False]*(n1)# 标记数字是否被使用defbacktrack(path):iflen(path)n:res.append(.join(f{x:5d}forxinpath))returnforiinrange(1,n1):ifnotused[i]:used[i]Truepath.append(i)backtrack(path)path.pop()used[i]Falsebacktrack([])print(\n.join(res))三、组合枚举生成所有k元子集LeetCode77题目核心给定n、k返回[1,n]中所有k个数的组合无序不重复。标准库解法itertools.combinationsfromtypingimportListfromitertoolsimportcombinationsclassSolution:defcombine(self,n:int,k:int)-List[List[int]]:numslist(range(1,n1))# 生成所有k元组合return[list(c)forcincombinations(nums,k)]样例输入n4,k2 → 输出6个组合。回溯剪枝高效手写版组合无需顺序用start避免重复剪枝可大幅提速。fromtypingimportListclassSolution:defcombine(self,n:int,k:int)-List[List[int]]:res[]defbacktrack(start,path):# 剪枝剩余元素不够凑k个直接返回iflen(path)(n-start1)k:returniflen(path)k:res.append(path.copy())returnforiinrange(start,n1):path.append(i)backtrack(i1,path)# 从下一个数开始避免重复path.pop()backtrack(1,[])returnres四、核心对比排列 vs 组合类型顺序函数典型场景排列有permutations排队、排序、序列组合无combinations/comb选人、选子集、方案数快速选择指南只求方案数→ 用math.comb组合数生成所有有序序列→ 用permutations或全排列回溯生成所有无序子集→ 用combinations或组合回溯算法竞赛/面试 → 必须掌握回溯模板内置函数可能受限总结组合数math.comb一步到位搭配取模适配大数场景全排列permutations快速生成回溯可处理自定义约束组合枚举combinations极简回溯剪枝更高效。吃透这3道题与两套写法Python 排列组合类题目直接秒杀。