Python组合数学

# Python组合数学 - 完整代码示例# 组合数学研究离散对象的计数、排列和组合结构import mathimport itertoolsfrom math import comb, permfrom scipy import special# 1. 基础计数排列与组合# 组合从 n 个元素中选 k 个不考虑顺序# 排列从 n 个元素中选 k 个考虑顺序n, k 10, 3n_comb comb(n, k) # C(10,3) 120n_perm perm(n, k) # P(10,3) 720print(f组合数 C({n},{k}) {n_comb})print(f排列数 P({n},{k}) {n_perm})print(f关系验证: P(n,k) C(n,k) * k! - {n_comb * math.factorial(k)} {n_perm})# 2. itertools 生成排列和组合items [A, B, C, D]# 生成所有 2-组合combs_2 list(itertools.combinations(items, 2))print(f\n从 {items} 中选 2 个的组合 ({len(combs_2)} 个):)for c in combs_2:print(f {c})# 生成所有 2-排列perms_2 list(itertools.permutations(items, 2))print(f\n从 {items} 中选 2 个的排列 ({len(perms_2)} 个):)for p in perms_2[:5]:print(f {p})print(f ... 共 {len(perms_2)} 个)# 生成所有排列n! 个all_perms list(itertools.permutations(items))print(f\n所有排列 (4! {len(all_perms)} 个))# 3. 二项式系数与帕斯卡三角形def pascal_triangle(n_rows):生成帕斯卡三角形杨辉三角triangle []for n in range(n_rows):row [comb(n, k) for k in range(n 1)]triangle.append(row)return trianglepascal pascal_triangle(10)print(f\n帕斯卡三角形 (前 10 行):)for i, row in enumerate(pascal):print(f n{i}: {row})# 4. 二项式定理验证# (xy)^n sum_{k0}^n C(n,k) * x^{n-k} * y^kdef binomial_expand_coeffs(n):返回 (xy)^n 展开的系数列表return [comb(n, k) for k in range(n 1)]n_binom 5coeffs binomial_expand_coeffs(n_binom)print(f\n(xy)^{n_binom} 的展开系数: {coeffs})# 验证系数之和 2^nprint(f系数之和: {sum(coeffs)} 2^{n_binom} {2**n_binom})# 5. 多重集组合# 从 n 类物品中选 k 个允许重复, C(nk-1, k)def multiset_combinations(n_types, k_pick):计算多重集组合数 C(nk-1, k)return comb(n_types k_pick - 1, k_pick)print(f\n多重集组合: 3 种类型选 4 个 C(34-1,4) {multiset_combinations(3, 4)})# 6. 斯特林数 (Stirling Numbers)# 第一类 Stirling 数将 n 个元素排列成 k 个循环# 第二类 Stirling 数将 n 个元素划分为 k 个非空子集n_stirling 7print(f\n第二类 Stirling 数 S({n_stirling}, k):)for k in range(1, n_stirling 1):s2 special.stirling(n_stirling, k, kind1)print(f S({n_stirling},{k}) {s2})# 7. 贝尔数 (Bell Numbers)# 将 n 个元素划分为非空子集的总方式数def bell_number(n):计算第 n 个贝尔数if n 0:return 1# B_n sum_{k1}^n S(n,k) 其中 S 是第二类 Stirling 数return sum(special.stirling(n, k, kind2) for k in range(1, n 1))print(f\n贝尔数:)for i in range(10):print(f B_{i} {bell_number(i)})# 8. 卡特兰数 (Catalan Numbers)# C_n (1/(n1)) * C(2n, n)def catalan(n):计算第 n 个卡特兰数return comb(2*n, n) // (n 1)print(f\n卡特兰数:)for i in range(10):print(f C_{i} {catalan(i)})# 9. 组合恒等式验证print(f\n组合恒等式验证:)# Pascal 恒等式: C(n,k) C(n-1,k) C(n-1,k-1)n_id, k_id 10, 4lhs comb(n_id, k_id)rhs comb(n_id - 1, k_id) comb(n_id - 1, k_id - 1)print(f Pascal: C({n_id},{k_id}) {lhs} C({n_id-1},{k_id}) C({n_id-1},{k_id-1}) {rhs})# Vandermonde: sum_i C(r,i) * C(s,n-i) C(rs,n)r, s, n_v 5, 3, 4vand_lhs sum(comb(r, i) * comb(s, n_v - i) for i in range(n_v 1))vand_rhs comb(r s, n_v)print(f Vandermonde: sum C({r},i)C({s},{n_v}-i) {vand_lhs} C({rs},{n_v}) {vand_rhs})# 10. itertools 高级用法笛卡尔积、幂集# 笛卡尔积colors [红, 蓝, 绿]sizes [S, M, L]cartesian list(itertools.product(colors, sizes))print(f\n笛卡尔积 ({len(cartesian)} 个):)for item in cartesian[:6]:print(f {item})# 幂集所有子集def powerset(iterable):生成所有子集幂集s list(iterable)return list(itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s) 1)))set_a [a, b, c]ps powerset(set_a)print(f\n幂集 (共 {len(ps)} 个子集): {ps})# 11. 整数划分函数def partition_count(n):计算整数 n 的划分数递归 记忆化memo {}def p(n, max_partNone):if max_part is None or max_part n:max_part nif n 0:return 1if max_part 0:return 0key (n, max_part)if key in memo:return memo[key]memo[key] p(n, max_part - 1) p(n - max_part, max_part)return memo[key]return p(n)print(f\n整数划分:)for i in range(1, 11):print(f p({i}) {partition_count(i)})# 12. 组合生成算法字典序下一组合def next_combination(comb_set, n):按字典序生成下一个组合k len(comb_set)result comb_set.copy()for i in range(k - 1, -1, -1):if result[i] n - k i:result[i] 1for j in range(i 1, k):result[j] result[j - 1] 1return resultreturn Nonecurrent [0, 1, 2]print(f\n字典序组合生成 (C(5,3)):)print(f 第一个: {current})for _ in range(5):current next_combination(current, 5)if current:print(f 下一个: {current})print(\n组合数学总结math.comb/perm 提供高效基础运算)print(itertools 生成组合对象scipy.special 提供高级组合函数)