集合分划Set Partitions— 5W1H故事与需求定义088集合分划与RGSWho谁实现者算法学习者、组合数学研究者使用者需要枚举等价关系或分组方案的程序员例如数据库查询优化等价类划分、机器学习聚类结果枚举、编译器寄存器着色等领域的开发者原著者Donald E. Knuth来自 TAOCP 第4卷 Fascicle 3BWhat什么集合分划算法枚举有限集合 {1, 2, …, n} 的所有划分方式等价关系。每种划分将集合分成若干非空、互不相交、合并为全集的子集称为块。核心数据结构是受限增长字符串Restricted Growth String, RGS长度为 n 的整数序列a[0..n-1]满足a[0] 0且对所有i 1a[i] max(a[0..i-1]) 1每个合法的 RGS 与一个集合分划一一对应分划总数由Bell 数给出B(0)1, B(1)1, B(2)2, B(3)5, B(4)15, B(5)52。When何时当需要穷举所有分组方案时n 通常较小n 12 时 Bell 数仍可管理在组合优化、测试用例生成、或数学软件中需要精确枚举时学习 TAOCP 第4卷组合算法章节时作为基础练习Where何处文件路径taocp_volume4/set_partition.c对应教材TAOCP 第4卷 Fascicle 3B第7.2.1.5节相关算法整数分划integer_partition.c、所有组合生成all_combinations.cWhy为何数学基础Bell 数和集合分划是组合数学的核心概念是理解等价关系、群论、信息论的基础应用价值数据库查询优化中的连接顺序枚举、编译器中的值编号分析均依赖集合分划算法技巧RGS 表示法使枚举算法简洁、字典序明确避免重复计数教学意义完整展示 Knuth 字典序枚举框架在集合分划问题上的应用How如何枚举算法字典序迭代法初始化a [0, 0, ..., 0]全零 RGS对应单一分划 {{1,2,…,n}}访问当前 RGS从右往左找第一个可以增大的位置i条件a[i] max(a[0..i-1]) 1若找不到这样的位置则枚举完毕将a[i]加 1将a[i1..n-1]重置为 0回到步骤 2Bell 三角形用于验证 Bell 数行0: 1 行1: 1 2 行2: 2 3 5 行3: 5 7 10 15每行第一个元素 上一行最后一个元素后续元素 前一个 上一行对应元素。需求定义需求 ID描述REQ-01实现gen_all_partitions(n, callback, userdata)通过回调函数逐一访问所有分划REQ-02实现bell_number(n)计算 Bell 数n 12REQ-03实现check_rgs(a, n)验证 RGS 合法性REQ-04不使用外部数学库仅依赖stdio.h、string.hREQ-05支持 n0 的边界情况返回 1 个分划即空集的唯一划分REQ-06n MAX_N10 的范围内不发生内存越界验收标准标准 ID验收条件AC-01bell_number(k)对 k0,1,2,3,4 分别返回 1,1,2,5,15AC-02gen_all_partitions(3, ...)恰好生成 5 个分划AC-03对 n5 生成的所有 52 个 RGScheck_rgs返回 1全部合法AC-04gen_all_partitions(4, ...)恰好生成 15 个分划AC-05gcc -stdc99 -Wall编译无警告无错误AC-06所有测试通过tests_failed 0程序返回 0
