前阵子一个推荐位脚本出了事。它要从 20 个候选商品里挑 5 个放进每日推荐位,按不同顺序展示。产品的预期很清楚:每天 15504 种组合。上线一周后,记录表一天写进了 186 万行,存储先撑不住了。
把数据拉出来一看,内容其实没错:去重之后正好还是 15504 种组合。问题在于脚本用排列数生成计划,把同一批商品的不同摆放顺序当成了不同的组合。5 个位置有 5! = 120 种排法,1860480 = 15504 × 120,差了整整 120 倍。
这是把「排列」和「组合」两个公式用混了。它们只差一个除以 k 的阶乘,但在代码里用错,代价可能是百倍的存储和完全对不上的统计。这篇就从这个坑出发,讲清排列与组合的区别、杨辉三角的递推、两种枚举写法、重复元素的去重、容斥与卡特兰数,最后给一个「什么时候不该枚举」的量级判断。
排列与组合:顺序算不算数
排列(permutation)是从 n 个不同元素里取 k 个,按顺序排成一列。第一个位置有 n 种选法,第二个位置剩 n-1 种,一直取到第 k 个,所以总数是 P(n,k) = n × (n-1) × ... × (n-k+1) = n!/(n-k)!。
组合(combination)是同样取 k 个,但不看顺序。它和排列的关系只有一步:每一组 k 个元素,自身可以排出 k! 种顺序,这些顺序在组合里都算同一个结果。所以 C(n,k) = P(n,k)/k! = n!/(k!(n-k)!)。
用 5 个人做对照。选 3 个人排队,第一个位置 5 种、第二个 4 种、第三个 3 种,共 5×4×3 = 60 种,这是 P(5,3)。选 3 个人进同一个小组,甲乙丙和丙乙甲是同一组,每个组被排了 3! = 6 次,所以只有 60/6 = 10 种,这是 C(5,3)。
排列:交换顺序算新结果
适合排班、座位、推荐位顺序、比赛名次。判断依据是「把两个元素对调,结果是否不同」。不同就乘上 k!,用 P(n,k)。
组合:交换顺序还是同一个
适合分组成员、候选集合、特征子集、A/B 实验分组。判断依据同样是对调两个元素,结果没变就不要再乘 k!,用 C(n,k)。
from math import comb, perm
print(perm(5, 3), comb(5, 3))
print(comb(20, 5), perm(20, 5))
print(perm(20, 5) // comb(20, 5))
在本机 Python 3.15 上跑,输出是:
60 10
15504 1860480
120
第三行的 120 就是开头那次事故的比例。产品要的是 15504 个不重复的商品集合,脚本给的是 186 万条带顺序的记录,两者都对「组合」这个词有自己的理解,但只有前者符合数学定义。
这里有一个容易踩的细节:分组场景里,如果两组人数固定,交换两组整体也会产生重复。比如把 10 个人分成两组各 5 人,C(10,5) = 252 算的是「先选 5 个进 A 组」的方案数;如果 A 组和 B 组没有名字上的区别,同一份划分会被算两次,正确结果是 126。公式没错,错在把有标签的分组当成了无标签的划分。
对称性:选中的和没选中的一一对应
组合数有一个很实用的对称性:C(n,k) = C(n,n-k)。从 n 个里选 k 个,等价于从 n 个里排除 n-k 个,每一种选法都唯一对应一种排除法,反过来也成立,所以两边的数量必然相等。
这个等式可以省掉大量计算。要算 C(100,98),按定义要乘 98 项,换成 C(100,2) 只需要 100×99/2 = 4950。代码里通常先做一步 k = min(k, n-k),让循环只跑较短的那一边。对 C(1000,999) 这种极端情况,这一步把 999 次乘法压成 1 次。
要注意,对称的是数量,不是集合。选中的 k 个和剩下的 n-k 个是互补的两个子集,内容不同,只是个数相同。写业务代码时如果混淆这一点,会得到「数量和预期一致、内容却完全相反」的结果,比如把「入选名单」和「淘汰名单」搞反。
对称性还有一个理论用途:它说明二项式系数在中间取得最大值。n 固定时,C(n,k) 随着 k 从 0 增到 n/2 单调上升,再对称地下降。这解释了为什么抽样的组合数在「取一半」时最大,也解释了为什么枚举到一半时最容易爆炸。
杨辉三角与递推:不用阶乘也能算
把组合数按 n 排成一行一行,就是杨辉三角。每个数等于它左上和右上两个数之和,写成公式是 C(n,k) = C(n-1,k-1) + C(n-1,k),边界是 C(n,0) = C(n,n) = 1。
这个递推可以用分类来证明。固定第 n 个元素,问「选不选它」:选它,剩下的 k-1 个要从前 n-1 个里选,方案数是 C(n-1,k-1);不选它,k 个全部从前 n-1 个里选,方案数是 C(n-1,k)。这两类互斥且穷尽,按加法原理相加就是全部方案。这也说明组合数的递推和上一篇的加法原理是同一件事。
row = [1]
for n in range(1, 8):
row = [1] + [row[k - 1] + row[k] for k in range(1, n)] + [1]
print(n, row)
1 [1, 1]
2 [1, 2, 1]
3 [1, 3, 3, 1]
4 [1, 4, 6, 4, 1]
5 [1, 5, 10, 10, 5, 1]
6 [1, 6, 15, 20, 15, 6, 1]
7 [1, 7, 21, 35, 35, 21, 7, 1]
用递推求组合数,最大的好处是避免阶乘先膨胀再相除。64 位有符号整数最大约 9.22 × 10^18,而 21! = 51090942171709440000,已经超过了这个范围。用阶乘公式算 C(30,15),中间量 30! 早就溢出了,哪怕最后结果 155117520 完全装得下。
递推只做加法,每一步的中间值都不会超过最终结果,所以不会出现「结果很小、中间量爆炸」的情况。时间复杂度是 O(nk),用滚动数组能把空间压到 O(k)。Python 的整数是任意精度,不会溢出,但大整数乘法仍然比加法慢;真要在 Python 里算 C(1000,500),结果有 300 位十进制,直接调 math.comb 比手写递推更省事。
枚举所有组合:回溯与位掩码
有些场景不能只算个数,还得把每一种组合列出来,比如生成测试用例、穷举参数、搜索子集。常见写法有两种,思路完全不同。
第一种是递归回溯。按位置从小到大选,每次从上一个元素之后继续挑,保证不重复也不遗漏。剩余元素不够凑满 k 个时直接返回,这一步剪枝能省掉大量无效分支。
def combos(n, k):
result = []
def walk(start, path):
if len(path) == k:
result.append(tuple(path))
return
for x in range(start, n - (k - len(path)) + 1):
path.append(x)
walk(x + 1, path)
path.pop()
walk(0, [])
return result
print(len(combos(5, 3)))
print(combos(5, 3))
10
[(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), (0, 3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
第二种是位掩码。把每个元素对应到二进制的一位,用 0 表示不选、1 表示选。枚举所有 n 位的掩码,只保留 1 的个数等于 k 的那些,再翻译成元素集合。
n, k = 5, 3
found = []
for mask in range(1 << n):
if mask.bit_count() == k:
found.append(tuple(i for i in range(n) if mask >> i & 1))
print(len(found))
print(found)
10
[(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3), (0, 1, 4), (0, 2, 4), (1, 2, 4), (0, 3, 4), (1, 3, 4), (2, 3, 4)]
两种写法结果数量一致,顺序不同:回溯按字典序输出,位掩码按掩码大小输出。位掩码的代码更短,但它的循环次数是 2^n,而不是 C(n,k)。n=30 时,掩码要检查 2^30 = 1073741824 次,而实际组合只有 C(30,15) = 155117520 个,前者是后者的将近 7 倍。n 一大,这个差距就很明显。
更根本的问题是绝对量级。C(30,15) 是 1.55 亿,按每秒处理 100 万条也要 155 秒;每条记录按 100 字节算,全存下来要 15 GB 左右。到 C(40,20) = 137846528820,已经是千亿级,任何单机枚举都不现实。所以工程上的判断顺序是:先算 math.comb(n,k),超过一千万就别想着枚举,改成随机采样、动态规划或者加约束剪枝。
重复元素的多重集排列
前面的公式都假设元素各不相同。现实数据经常不是这样,比如订单里有多个相同模板,或者字符串里有重复字母。这时同样的排列公式会多算。
以字符串 AAB 为例。三个字符如果互不相同,排列数是 3! = 6;但两个 A 互换位置得到的字符串完全一样,这 6 种里每两种重复一次,实际只有 3 种。公式是把总数除以各重复元素个数的阶乘:3!/(2!×1!) = 3。
from itertools import permutations
print(sorted(set(permutations("AAB"))))
输出是:
[('A', 'A', 'B'), ('A', 'B', 'A'), ('B', 'A', 'A')]
一般形式是 n!/(n1! × n2! × ... × nm!),其中 n1 到 nm 是各类重复元素的个数,它们的和等于 n。AABB 就是 4!/(2!×2!) = 6,确实能列出来 6 种。
为什么不能直接用 n!:每一个真实排列,在「把相同元素当成不同个体」的计数里,会被重复数 n1! × n2! × ... 次。AAB 里两个 A 被当成 A1 和 A2,每种真实排列对应 2 种带下标的排列,所以除以 2 正好修正。
真实场景也是这个数法。10 个展示位要放 4 个相同模板和 6 个不同商品,如果只关心模板的位置,方案数是 10!/4! = 151200。另一种写法是先枚举 10! 再去重,得到 362 万条中间结果;n 再大一点,比如 20,中间结果就是 2.4 × 10^18,还没去重就先爆了。公式和枚举的差别,在这里就是「一秒」和「不可能」的差别。
容斥:数「至少一个」
组合计数里最常出现的句式是「至少满足一个条件」。直接数很难,因为条件之间会重叠;用容斥把它拆成「满足这个」「满足那个」「同时满足」几部分,就好算了。
两个集合的版本:|A ∪ B| = |A| + |B| - |A ∩ B|。100 名学生里,60 人选了 Python 课,45 人选了 Go 课,25 人两门都选。至少选一门的人数是 60 + 45 - 25 = 80,两门都没选的是 20 人。
三个集合的版本多两项:|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|。假设三个课程的人数分别是 60、45、40,两两都选的是 25、20、15,三门都选的是 10,至少选一门的人数就是:
py, sql, go = 60, 45, 40
py_sql, py_go, sql_go, all3 = 25, 20, 15, 10
union = py + sql + go - py_sql - py_go - sql_go + all3
print(union)
95
结果是 95。可以验算一下:单集合相加得 145,减去三对交集 60 得 85,此时三门都选的人被减了三次、加了三次,净效果是少算一次,所以再加 10 得 95。符号规律是「奇数个集合的交加,偶数个集合的交减」。
容斥的价值在于它把「至少一个」翻译成了若干个好数的项。它也有代价:m 个集合要展开 2^m - 1 项,m=10 就是 1023 项。集合一多,公式还在,但手算和直接枚举都不现实,通常改用动态规划或者按位统计。
还有一个常用的补集技巧:如果「一个都不满足」比「至少一个」好数,就先数补集,再用总数减掉。这和第 6 节开头的思路一样,只是方向反过来。
卡特兰数:被约束的排列
有一类计数问题,答案既不是排列也不是组合,而是卡特兰数(Catalan number)。它的公式是 Cat(n) = C(2n,n)/(n+1),前几项是 1、1、2、5、14、42、132、429、1430。
from math import comb
print([comb(2 * n, n) // (n + 1) for n in range(9)])
[1, 1, 2, 5, 14, 42, 132, 429, 1430]
最典型的场景是括号匹配:n 对括号有多少种合法写法。n=3 时,所有由 3 个左括号和 3 个右括号组成的字符串共有 C(6,3) = 20 种,但合法的只有 5 种,因为任意前缀里右括号的数量不能超过左括号。
为什么不是 2^n:有人觉得每对括号只有「放左边」和「放右边」两种选择,所以是 2 的 n 次方。这个想法漏掉了两个约束:左右括号的总数必须相等,且任何前缀都不能出现「右括号多于左括号」。n=3 时 2^3 = 8,既不是全部 20 种候选,也不是合法的 5 种,纯属巧合地接近。
合法的数量可以用总数减去非法数得到:C(6,3) - C(6,4) = 20 - 15 = 5。一般地,非法串和「多一个右括号」的串一一对应,所以非法数是 C(2n,n+1),两者相减正好等于 C(2n,n)/(n+1)。
出栈序列是同一个数列。n 个元素依次进栈,随时可以出栈,问有多少种不同的出栈顺序。n=3 时是 5 种,不是 3! = 6,也不是 8。下面用模拟验证:对每一个排列,按「需要谁就把谁之前没进栈的都压进去」的方式走一遍,走不通的就排除。
from itertools import permutations
def valid(seq):
stack, nxt = [], 1
for x in seq:
while nxt <= x:
stack.append(nxt)
nxt += 1
if stack.pop() != x:
return False
return True
print([p for p in permutations(range(1, 4)) if valid(p)])
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 2, 1)]
五种都在,唯独没有 (3, 1, 2)。原因是想第一个弹出 3,必须先把 1、2、3 都压进去,此时栈顶是 3,弹出后栈顶是 2,不可能先弹出 1。这个约束和括号匹配的「前缀不能右多于左」是同一件事,所以数量也相同。
卡特兰数还出现在二叉树形态计数、凸多边形三角剖分数、网格路径不越过对角线等场景。它的共同点是「有一类前缀约束」,看到这类约束就该想到它,而不是硬套排列组合。
一张现象对照表
下面这些现象在推荐、实验平台、离线任务里都出现过,原因基本都能回到「有序还是无序」「该不该枚举」这两个判断上。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 记录条数是预期的 120 倍,去重后却正常 | 把组合当排列,同一集合的不同顺序被写成多条 | 看代码用的是 perm 还是 comb,再算 k! 是不是那个倍数 |
| 分组后两组人数不等,还有用户重复 | 分组是无序划分,却按有标签的排列抽样 | 确认组是否有名字,是否需要整体除以组数的阶乘 |
| 枚举脚本跑到内存溢出 | 组合数指数增长,C(30,15) 已经是 1.55 亿 | 先算 math.comb(n,k),再决定枚举还是采样 |
| 组合数算出来是负数或 0 | 用 64 位整数存阶乘,21! 就溢出了 | 改用递推、大整数,或者在模意义下计算 |
| 取模后的组合数和精确值对不上 | 模运算下不能直接做除法,要用逆元 | 检查是否用了 pow(den, MOD-2, MOD),MOD 是否为素数 |
| 重复元素的排列数偏多 | 相同元素被当成不同个体,直接用了 n! | 数清每类重复元素的个数,除以各自的阶乘 |
| 容斥算出的并集偏小 | 漏加三重交集,或者符号写反 | 用三个集合的小例子手算,和代码结果对拍 |
边界与代价
第一,组合数增长极快,不能当普通整数随便存。C(1000,500) 有 300 位十进制,C(2000,1000) 更大,连打印都费劲,更不用说放进浮点数。需要精确值时用 Python 的大整数或者专门的大数库;只需要模值时,全程在模意义下算,别先算精确值再取模。
第二,模运算下不能直接除。C(n,k) = n!/(k!(n-k)!) 里的除法,在模意义下要换成乘逆元。前提是分母与模数互素,工程上通常要求模数是素数且 n 小于模数。不满足时要换卢卡斯定理或者别的方法。直接写整数除法,得到的是 0 或者错误结果,而且不会报错。
第三,枚举和采样是两种代价完全不同的做法。枚举保证不遗漏,但规模一大就不可行;采样能处理大 n,但结果是近似的,精度大约按 1/sqrt(样本数) 提升,而且稀有组合可能一次都采不到。要覆盖边界情况,采样之外还得补定向用例。
第四,去重需要额外内存。用集合存元组,每个元素都有对象头和哈希表的开销,百万级就要几百兆。数据量再大,得改成排序后归并去重,时间换成 O(n log n),内存压力小一些。
第五,卡特兰数只适用于有特定前缀约束的结构。括号匹配、出栈序列、二叉树形态都满足同一类约束,所以共用同一个公式;换成「允许两种括号」或者「允许任意嵌套深度」,答案就变了,不能照搬。
第六,容斥的项数按集合数指数增长。两三个集合还能手算,十个集合就是 1023 项。实际工程里更常用的是按位枚举子集加容斥,或者直接上动态规划,公式只用来做小规模校验。
小结与练习
这篇的主线可以压成四句。排列看顺序,组合不看顺序,两者只差一个 k!;组合数可以用杨辉三角的加法递推来算,避免阶乘先膨胀再相除;枚举要么回溯、要么位掩码,动手前先用 math.comb 估一下量级;带重复元素要除以各类阶乘,带「至少一个」的条件用容斥,带前缀约束的计数多半是卡特兰数。
回到开头那次事故:如果脚本在生成计划前先算一下 comb(20,5) = 15504,再确认「顺序算不算新结果」,就不会写出 120 倍的记录。公式本身不难,难的是先判断清楚问题属于哪一种。
当天可以自己验证的练习:
- 用
math.perm(5,3)和math.comb(5,3)验证 60 和 10,再用文中的回溯与位掩码各枚举一次,确认两边都是 10 组。 - 用杨辉三角的递推算
C(30,15),和math.comb的结果对照;再算C(1000,500)的十进制位数,确认是 300 位。 - 用 AAB 和 AABB 验证多重集排列公式,并解释为什么 3 个字符不能直接用
3! = 6。 - 用 3 个元素枚举所有出栈序列,确认只有 5 种,并指出
(3,1,2)为什么不可能。 - 自己设计一个三集合的容斥例子,先手算并集,再用 Python 验证;然后把其中一个交集改大,观察并集是否超过总数,并解释这说明数据哪里不自洽。
离散数学这一组到这里就收尾了。集合与关系给了结构,逻辑给了判断,递推与归纳给了构造,鸽巢给了下界,组合计数给了数量。这几件工具的共同点是:它们都只在有限、离散的对象上工作。下一组微积分要换一套语言,从离散求和走向连续累积:把一项一项地加变成连续地积,把差分变成导数,把求和变成积分。先看清楚「离散」和「连续」的边界,再进入那一组,会顺很多。