🔢 mathematics

Benchmarking of algorithms for set partitions

本文回顾了用于枚举集合划分的算法，提供了其计数的近似公式，并根据基准测试推荐了 Djokic 等人的算法。

原作者： Arnav Khinvasara, Alexander Pikovski

发布于 2026-02-03

📖 1 分钟阅读🧠 深度阅读

原作者： Arnav Khinvasara, Alexander Pikovski

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你有一盒各不相同的乐高积木。你的任务是找出将这些积木进行分组的所有可能方式。你可以把每块积木都放在自己的小堆里，也可以把它们全部堆成一座巨大的高塔，或者将它们混合搭配成各种不同的簇。在数学世界中，这被称为集合划分（set partition）。

这篇论文本质上是一份关于尝试列出所有这些可能分组的计算机程序的“比赛报告”。以下是作者的研究发现，使用了简单的类比：

1. 问题所在：快速爆炸的谜题

作者解释说，虽然列出少量物品的分组听起来很简单，但可能性的数量会爆炸式增长。

类比： 这就像是一个抢座位的游戏，只不过参与者不是人，而是数字。如果有 3 个项目，有 5 种分组方式。但当达到 17 个项目时，会有大约 820 亿种不同的分组方式。
现实情况： 如果你有超过 17 或 18 个项目，让计算机在合理的时间内列出每一个分组是不可能的。然而，对于较小的数字，让计算机完成这项工作是非常有用的，特别是在处理像装箱或排班表这类优化任务时。

2. 计算可能性（“贝尔数”）

在开始对算法进行竞赛之前，作者需要一种方法来准确知道可以预期多少个分组。这些数字被称为贝尔数（Bell Numbers）。

挑战： 计算精确的数量非常困难，因此数学家使用公式来进行估算。
发现： 作者测试了几种复杂的数学公式。他们发现一种特定的公式（涉及一个被称为“兰伯特 W 函数”的特殊数学函数）极其精确。这就像拥有一个即使对于小规模项目也能精确到分钟的天气预报。他们还发现了一种更简单的公式，它在处理较小组别时表现良好，但随着数字变得巨大，它会变得有些不准确。

3. 比赛：四种算法的竞争

论文的核心部分是一个“基准测试（benchmark）”，这只是一个时髦的说法，指的就是一场计时赛。作者将四种旨在列出这些分组的不同计算机程序（算法）放在各种计算机（笔记本电脑、台式机、云服务器）上运行，并使用了不同的软件工具（编译器）和操作系统（Windows 和 Linux）。

这四位参赛者分别是：

Hutchinson 算法： “老前辈”。这是几十年前的经典方法。
Semba 算法： 一位现代且快速的竞争者。
Er 算法： 另一位现代且快速的竞争者。
Djokic 等人的算法： 最新的挑战者。

结果：

老前辈 (Hutchinson)： 这个程序的运行速度明显慢于其他程序。它就像穿着沉重的靴子跑马拉松。作者明确表示：不要使用这个。
现代选手 (Semba, Er, Djokic)： 它们要快得多。
冠军： Djokic 的算法摘得了金牌。它是表现最出色的，也是最快的。

4. “引擎”同样重要

作者还发现，运行代码的“引擎”与汽车本身一样重要。

操作系统： 在 Linux 上运行的代码通常比在 Windows 上更快。
编译器： 将代码翻译成机器语言的工具也会产生巨大的差异。例如，在一种特定的算法上，Intel 编译器比标准的 GNU 编译器快得多；但在另一种算法上，GNU 编译器反而更快。
启示： 要获得最佳速度，你需要正确的算法以及正确的软件设置。

5. 最终建议

在进行了数千次测试后，作者为任何需要进行此类工作的人给出了明确的结论：

使用 Djokic 等人的算法。 它是最快的，而且相对较短（易于编写），并且易于实现。
提示： 请确保你的计算机设置为“高性能”模式（编译器优化级别 2 或更高），如果你使用的是 Linux，请使用 Intel 编译器以获得最佳效果。

他们未涵盖的内容

作者谨慎地坚持在基础范围内进行讨论。他们没有测试那些试图寻找带有特定限制的分组（例如“每组最多只能有 3 个项目”）的算法，也没有研究一种称为“格雷码（Gray codes）”的不同类型的排序系统。这些内容留作未来的研究。

总结： 如果你需要计算机列出一组小型项目的每一种分组方式，不要使用旧方法。使用 Djokic 算法，在 Linux 上运行并配合 Intel 编译器，你就能在眨眼之间完成任务。

技术摘要：集合划分算法基准测试

问题陈述

本文探讨了枚举 $n$ 个不同对象的所有可能集合划分（set partitions）的计算挑战。集合划分被定义为一组不重叠的子集（块）的集合，其并集构成了原始集合。这一问题在组合优化任务中具有基础性意义，例如在需要根据特定标准将物体分配到组中的场景（如将物品装入包裹、调度或将菜肴分配到盘中）。

虽然对于较小的 $n$ ，全量枚举是可行的，但划分的数量随之迅速增长（贝尔数， $B_n$ ）。例如，当 $n=17$ 时，存在约 $8 \times 10^{10}$ 个划分，这使得在大规模 $n$ 的情况下，若没有显著的计算资源支持，穷举搜索是不可行的。本文旨在填补文献中的空白，通过对现有算法进行实际的性能对比，而以往的研究缺乏对现代方案与经典方法进行直接性能基准测试的研究。

方法论

作者采用了经验性的基准测试方法，而非理论复杂度分析，理由是针对这些特定算法缺乏明确的理论运行时间分析。研究方法包括：

算法选择： 选择了四种非递归（迭代）算法进行测试：
- Hutchinson [7]： 一种经典算法。
- Semba [12]： 一种现代快速算法。
- Er [4]： 一种利用格雷码（Gray code）概念但不进行显式构造的现代算法。
- Djokic et al. [3]： 一种现代快速算法。
- 注：由于重复函数调用带来的开销通常使得递归算法效率低于迭代方法，因此在基准测试中排除了递归算法。虽然提到了格雷码构造，但并未对其进行测试。
实验设置：
- 硬件： 测试在笔记本电脑、本地 PC 和云虚拟化机器上进行。
- 软件环境： 算法使用 C 语言实现以确保二进制文件轻量化。测试在 Linux 和 Windows 操作系统上均有运行。
- 编译器： 使用了 GNU C 编译器 (GCC)、Intel C 编译器 (ICC) 和 Microsoft Visual C (MSVC)，并配合各种优化级别。
分析部分： 本文还回顾了贝尔数 ( $B_n$ ) 的数学性质。评估了各种渐近公式和近似公式，以确定在处理小规模和大规模集合时，用于估算 $B_n$ 最实用的表达式。

核心贡献

1. 贝尔数的近似公式

作者评估了用于计算集合划分数量的现有渐近表达式。他们指出，由 Moser 和 Wyman [10] 利用 Lambert $W$ 函数推导出的特定近似公式在实际应用中最为准确：
$B_n \approx B^*_n = \frac{e^{n W(n) + n/W(n) - n - 1}}{\sqrt{W(n) + 1}} \left( 1 - \frac{W(n)^2(2W(n)^2 + 7W(n) + 10)}{24n(W(n) + 1)^3} \right)$
作者指出，该公式在 $2 \le n \le 50$ 时相对误差小于 $3 \times 10^{-3}$ ，并且在 $1 \le n \le 7$ 时能得出精确的整数值。他们还回顾了 Berend 和 Tassa [1] 的一个上界，指出尽管该上界在较大 $n$ 时会高估，但在较小的 $n$ 时仍具实用价值。

2. 经验基准测试结果

核心贡献是对四种算法的比较性能分析。主要发现包括：

编译器与操作系统的依赖性： 运行时间性能对编译器和操作系统高度敏感。基于 Linux 的代码（GCC/ICC）通常比基于 Windows 的代码（MSVC）快达 2 倍。编译器选择显著影响性能；例如，Hutchinson 算法在 GCC 上比在 ICC 上运行更快，而 Djokic 算法在 ICC 上的运行速度明显快于 GCC。
算法性能：
- Hutchinson [7]： 始终是最慢的算法，其性能随 $n$ 的增加而显著下降。
- Semba [12] 和 Er [4]： 表现优于 Hutchinson，但慢于 Djokic 算法。
- Djokic et al. [3]： 在测试范围（ $n=8$ 到 $n=15$ ）内展示了最快的执行时间。例如，在 $n=15$ 时，在 Linux/GCC 环境下，Djokic 算法耗时 3,746 ms，而 Semba 为 5,285 ms，Hutchinson 则需 30,512 ms。

结果与建议

基于经验数据，作者得出结论：建议在实际中使用 Djokic 等人 [3] 的算法。 作者强调，该算法不仅速度最快，而且实现相对简短且易于编写。

具体的实现建议包括：

使用 2 级或更高等级的编译器优化。
在 Linux 系统上利用 Intel 编译器 (ICC) 来运行 Djokic 算法，因为在他们的测试中，ICC 比 GCC 产生了更快的代码。
在补充代码中提供 Djokic 算法的实现。

重要性与范围

本文谦逊地声称填补了文献中的实际空白，即提供了集合划分生成算法的直接经验对比，而此前此类研究较为匮乏。它为现代硬件和编译器上的性能建立了一个基准。

作者明确限定了研究范围：

他们未涵盖基于硬件的枚举（参考 [2] 关于该主题的内容）。
他们未研究受限集合划分（具有最大块大小限制的划分），尽管他们指出这是一个需要单独调查的相关问题。
他们未对基于格雷码的算法进行基准测试，并将其作为未来的潜在研究方向。
他们未对编译器优化与硬件之间的相互作用进行深入的理论分析，认为这超出了本文的研究范围。

本文为需要枚举集合划分的研究人员和工程师提供了一份实用的指南，既提供了用于估算的数学工具，也提供了目前可用的最高效生成算法的验证性建议。