🔢 mathematics

Benchmarking of algorithms for set partitions

This paper reviews algorithms for enumerating set partitions, provides approximate formulas for their counts, and recommends the algorithm by Djokic et al. based on benchmarking tests.

Original authors: Arnav Khinvasara, Alexander Pikovski

Published 2026-02-03

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Arnav Khinvasara, Alexander Pikovski

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a box of distinct Lego bricks. Your job is to figure out every single way you can group these bricks together. You could put each brick in its own little pile, you could stack them all into one giant tower, or you could mix and match them into various clusters. In the world of math, this is called a set partition.

This paper is essentially a "race report" for computer programs that try to list every single one of these possible groupings. Here is the breakdown of what the authors found, using simple analogies:

1. The Problem: A Rapidly Exploding Puzzle

The authors explain that while listing groupings sounds easy for a few items, the number of possibilities explodes incredibly fast.

The Analogy: Think of it like a game of musical chairs, but instead of people, you have numbers. With just 3 items, there are 5 ways to group them. But by the time you have 17 items, there are about 82 billion different ways to group them.
The Reality: If you have more than 17 or 18 items, it becomes impossible for a computer to list every single grouping in a reasonable amount of time. However, for smaller numbers, it is very useful to have a computer do this, especially for optimization tasks like packing boxes or scheduling shifts.

2. Counting the Possibilities (The "Bell Numbers")

Before they could race the algorithms, the authors needed a way to know exactly how many groupings to expect. These numbers are called Bell Numbers.

The Challenge: Calculating the exact number is hard, so mathematicians use formulas to estimate it.
The Discovery: The authors tested several complex math formulas. They found one specific formula (involving a special math function called the "Lambert W function") that is incredibly accurate. It's like having a weather forecast that is right down to the minute, even for small numbers of items. They also found a simpler formula that works well for smaller groups but gets a bit sloppy as the numbers get huge.

3. The Race: Four Algorithms Competing

The main part of the paper is a "benchmark," which is just a fancy word for a timed race. The authors took four different computer programs (algorithms) designed to list these groupings and ran them on various computers (laptops, desktops, cloud servers) using different software tools (compilers) and operating systems (Windows and Linux).

The four racers were:

Hutchinson's Algorithm: The "Old Timer." This is the classic method from decades ago.
Semba's Algorithm: A modern, fast contender.
Er's Algorithm: Another modern, fast contender.
Djokic et al.'s Algorithm: The newest challenger.

The Results:

The Old Timer (Hutchinson): This program was significantly slower than the others. It's like trying to run a marathon in heavy boots. The authors explicitly say: Do not use this one.
The Modern Racers (Semba, Er, Djokic): These were much faster.
The Winner: Djokic's algorithm took the gold medal. It was the fastest across the board.

4. The "Engine" Matters Too

The authors also discovered that the "engine" running the code matters just as much as the car itself.

Operating Systems: Code running on Linux was generally faster than on Windows.
Compilers: The tool used to translate the code into machine language made a huge difference. For example, on one specific algorithm, the Intel compiler was much faster than the standard GNU compiler, but for another algorithm, the GNU compiler was faster.
The Takeaway: To get the best speed, you need the right algorithm and the right software settings.

5. The Final Recommendation

After running thousands of tests, the authors have a clear verdict for anyone who needs to do this work:

Use the algorithm by Djokic et al. It is the fastest, it is relatively short (easy to write), and it is easy to implement.
Tip: Make sure your computer is set to "high performance" mode (compiler optimization level 2 or higher) and, if you are on Linux, use the Intel compiler for the best results.

What They Didn't Cover

The authors were careful to stick to the basics. They did not test algorithms that try to find groupings with specific limits (like "groups can only have 3 items max"), nor did they look at a different type of ordering system called "Gray codes." Those are left for future research.

In summary: If you need a computer to list every way to group a small set of items, don't use the old methods. Use the Djokic algorithm, run it on Linux with the Intel compiler, and you'll get the job done in the blink of an eye.

Technical Summary: Benchmarking of Algorithms for Set Partitions

Problem Statement

The paper addresses the computational challenge of enumerating all possible set partitions for a set of $n$ distinct objects. A set partition is defined as a collection of non-overlapping subsets (blocks) whose union constitutes the original set. This problem is fundamental to combinatorial optimization tasks where one must identify an optimal distribution of objects into groups based on specific criteria (e.g., packing items into parcels, scheduling, or assigning dishes to plates).

While full enumeration is feasible for small $n$ , the number of partitions grows rapidly (Bell numbers, $B_n$ ). For instance, at $n=17$ , there are approximately $8 \times 10^{10}$ partitions, rendering exhaustive search infeasible for larger $n$ without significant computational resources. The paper aims to bridge a gap in the literature by providing a practical comparison of existing algorithms for generating these partitions, as previous studies lacked a direct performance benchmarking of modern proposals against classical methods.

Methodology

The authors employed an empirical benchmarking approach rather than a theoretical complexity analysis, citing the lack of clear theoretical runtime analysis for these specific algorithms. The methodology involved:

Algorithm Selection: Four non-recursive (iterative) algorithms were selected for testing:
- Hutchinson [7]: A classical algorithm.
- Semba [12]: A modern fast algorithm.
- Er [4]: A modern algorithm utilizing Gray code concepts without explicit construction.
- Djokic et al. [3]: A modern fast algorithm.
- Note: Recursive algorithms were excluded from benchmarking due to the overhead of repeated function calls, which generally makes them less efficient than iterative approaches. Gray code constructions were acknowledged but not tested.
Experimental Setup:
- Hardware: Tests were conducted on laptops, local PCs, and cloud virtualized machines.
- Software Environment: Algorithms were implemented in C to ensure lightweight binaries. Tests ran on both Linux and Windows operating systems.
- Compilers: The GNU C Compiler (GCC), Intel C Compiler (ICC), and Microsoft Visual C (MSVC) were utilized with various optimization levels.
Analytical Component: The paper also reviewed mathematical properties of Bell numbers ( $B_n$ ). It evaluated various asymptotic and approximate formulas to determine the most practical expressions for estimating $B_n$ across small and large set sizes.

Key Contributions

1. Approximation Formulas for Bell Numbers

The authors evaluated existing asymptotic expressions for calculating the number of set partitions. They identified a specific approximation derived by Moser and Wyman [10] using the Lambert $W$ function as the most accurate for practical use:
$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)$
The authors note that this formula provides a relative error smaller than $3 \times 10^{-3}$ for $2 \le n \le 50$ and yields the exact integer value for $1 \le n \le 7$ . They also reviewed an upper bound by Berend and Tassa [1], noting its utility for small $n$ despite overestimating for larger $n$ .

2. Empirical Benchmarking Results

The core contribution is the comparative performance analysis of the four algorithms. Key findings include:

Compiler and OS Dependence: Runtime performance is highly sensitive to the compiler and operating system. Linux-based code (GCC/ICC) generally outperformed Windows-based code (MSVC) by up to a factor of 2. Compiler choice significantly impacted performance; for instance, Hutchinson's algorithm ran faster on GCC than ICC, whereas Djokic's algorithm ran significantly faster on ICC than GCC.
Algorithm Performance:
- Hutchinson [7]: Consistently the slowest algorithm, with performance degrading significantly as $n$ increases.
- Semba [12] and Er [4]: Performed faster than Hutchinson but were slower than Djokic's algorithm.
- Djokic et al. [3]: Demonstrated the fastest execution times across the tested range ( $n=8$ to $n=15$ ). For example, at $n=15$ , Djokic's algorithm required 3,746 ms, compared to 5,285 ms for Semba and 30,512 ms for Hutchinson (on a Linux/GCC setup).

Results and Recommendations

Based on the empirical data, the authors conclude that the algorithm by Djokic et al. [3] is the recommended choice for practical use. The authors highlight that this algorithm is not only the fastest but also relatively short and easy to implement.

Specific implementation recommendations include:

Using compiler optimization level 2 or higher.
Utilizing the Intel Compiler (ICC) on Linux systems for the Djokic algorithm, as it yielded faster code than GCC in their tests.
Providing the implementation of the Djokic algorithm in the supplementary code.

Significance and Scope

The paper modestly claims to fill a practical gap in the literature by providing a direct, empirical comparison of set partition generation algorithms, which had previously been lacking. It establishes a baseline for performance on modern hardware and compilers.

The authors explicitly limit the scope of their study:

They do not cover hardware-based enumeration (referencing [2] for that topic).
They do not investigate restricted set partitions (partitions with a maximal block size), though they note this as a related problem requiring separate investigation.
They do not benchmark Gray-code based algorithms, suggesting this as a potential area for future work.
They do not provide a deep theoretical analysis of compiler optimization interplay with hardware, noting this is outside the scope of the work.

The paper serves as a practical guide for researchers and engineers needing to enumerate set partitions, offering both mathematical tools for estimation and a verified recommendation for the most efficient generation algorithm currently available.