New analysis reveals which algorithm fastest for enumerating set partitions

Researchers have studied computational approaches to counting and listing set partitions—a fundamental problem in discrete mathematics and optimization. The work, posted to arXiv, addresses both how to efficiently approximate these counts and which algorithm performs best in practice.

Approximating partition counts#

Set partitions represent ways to divide a collection of distinct objects into non-overlapping groups. The number of possible partitions grows explosively—known mathematically as the Bell number—and lacks a simple closed-form formula.

The researchers surveyed existing approximation methods and found that an older asymptotic formula developed by Moser and Wyman delivers remarkably accurate estimates even for smaller set sizes. A simpler approach by Berend and Tasssa also works well for modest-sized inputs, making it practical for quick estimates without heavy computation.

Finding the fastest enumeration approach#

Beyond counting, many real-world optimization problems require actually listing all set partitions. The authors reviewed non-recursive enumeration algorithms and compared four methods empirically: the classic Hutchinson algorithm and three modern alternatives.

All algorithms scaled exponentially with input size, as expected. However, the algorithm developed by Djokic and colleagues outperformed the others in benchmarks, making it the recommended choice for systems that need to generate partition lists efficiently.

The findings, submitted in February 2026 and revised in October, reflect ongoing interest in making combinatorial algorithms both faster and more accessible.