Benchmarking of algorithms for set partitions
Arnav Khinvasara, Alexander Pikovski · 2026
Read Benchmarking of algorithms for set partitions by Arnav Khinvasara, Alexander Pikovski (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-01350.txt.
Introduction
Arnav Khinvasara and Alexander Pikovski survey ways to count and list set partitions, splits of distinct items into groups. Partition counts, the Bell numbers, climb fast and lack a closed form, so the team tests literature guesses. A Moser-Wyman asymptotic guess proves shockingly true even for small sets, while a plain Berend-Tassa guess serves handily there. For listing, they weigh non-recursive plans with no Gray-code tricks, pitting Hutchinson's classic against three newer ones. All scale exponentially, with Djokic and co-authors' plan fastest in practice.
Catalog record
| CREATOR | Arnav Khinvasara, Alexander Pikovski |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 12233 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602.01350
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Benchmarking of algorithms for set partitions Arnav Khinvasara, Alexander Pikovski Abstract . Set partitions are arrangements of distinct objects into groups. The problem of listing all set partitions arises in a variety of settings, in particular in combinatorial optimization tasks. After a brief review, we give practical approximate formulas for determining the number of set partitions, both for small and large set sizes. Several algorithms for enumerating all set partitions are reviewed, and benchmarking tests were conducted. The algorithm of Djokic et al. is recommended for practical use. 1. Introduction A set partition is an arrangement of n distinct objects into groups. More formally, a partition of a set is a collection of non-overlapping sets (called groups or blocks) whose union is the original set. For example, the set \{1,2,3\} has five partitions in total: (\{1\},\{2\},\{3\}) , (\{1,2\},\{3\}) , (\{1,3\},\{2\}) , (\{1\},\{2,3\}) , (\{1,2,3\}) . In practical problems, set partitions arise in a variety of settings. Usually one wants to find an optimal way to distribute n objects into groups according to certain criteria. If n is not too large, one can enumerate all possible set partitions and use a full search to find the optimal one. The total number of set partitions is a rapidly increasing number (see discussion below), and already for n=17 we have about 8\cdot 10^{10} partitions. Thus, for n larger than 17 or 18 (depending on the computational resources) listing all partitions is not feasible. Still, it is a problem of practical importance to list all set partitions for a given n , if it is not too large. After a brief review of applications of set partitions, we discuss the number of set partitions (Bell numbers) and approximate formulas to calculate them. Then, we discuss and benchmark four algorithms for generating all set partitions, a classical one and three modern ones. We conclude by recommending the algorithm with the best performance and give an outlook to topics outside the scope of this study. The problem of enumerating set partitions in hardware, as opposed to software, is considered in ( 2 ) . 2. Examples how set partitions arise in practice A common problem which leads to set partitions is: What are the placements of n distinct items in at most n boxes? Similarly, set partitions arise in questions of the following type: What are the possible ways to serve n dishes on plates? What are the possible ways to sit n people at tables? What are the possible “rhyme schemes” for n lines? (E. g. for 3 lines we have the 5 patterns abc , aab , aba , abb , aaa .) Determining all set partitions has practical relevance in the setting of an optimization problem. Imagine you have n different items that need to be packed and shipped. Each parcel may contain one or more items. There are certain constraints (size, weight, …) which are case-specific. The way to go about solving this problem algorithmically is to check all possible ways to pack the items, calculating the case-specific constraints for each one, and then choose the optimal one. Further applications of set partitions, among others to scheduling problems, are discussed in ( 6 ) . 3. Number of set partitions (Bell numbers) The number of set partitions of a set of size n is called the Bell number B_{n} . The mathematical properties of Bell numbers are well-studied, see e. g. ( 11 ) . To calculate Bell numbers, one can use for example the following recursion (for further recursions, see ( 13 ) ): (1) B_{n}=1+\sum_{k=1}^{n-1}\binom{n-1}{k}B_{k}. This formula may be illustrated using the example of packing n items in boxes as follows. Look at one specific item. This item goes either alone in a box, or with k items. There are \binom{n-1}{k} choices to find k box neighbours for this item, and the remaining n-k-1 items can be packed in B_{n-k-1} ways in other boxes, for k=0\ldots n-2 ; the case k=n-1 (all items on one box) in addition contributes one. Thus in total, we have \sum_{k=0}^{n-2}\binom{n-1}{k}B_{n-k-1}+1 ways to pack n items, which, after simplification, is the same as Eq. 1 . Since the calculation of Bell numbers requires computer-algebra packages, for convenience, we give a list of the first 20 Bell numbers in Table 1 . n Number of set partitions B_{n} n Number of set partitions B_{n} 1 1 11 678,570 2 2 12 4,213,597 3 5 13 27,644,437 4 15 14 190,899,322 5 52 15 1,382,958,545 6 203 16 10,480,142,147 7 877 17 82,864,869,804 8 4,140 18 682,076,806,159 9 21,147 19 5,832,742,205,057 10 115,975 20 51,724,158,235,372 Table 1. Number of set partitions (Bell numbers). A large variety of different asymptotic and approximate expressions are noted in the literature ( 8 ; 9 ; 5 ) . We reviewed the different expressions and compared them numerically with exact values, to determine the most useful ones for practical use. Remarkably, we found that several asymptotic expressions for B_{n} give a very good approximation even at small values of n . The best one is the following. The unique solution to the equation \eta e^{\eta}=x (for positive x ), is conventionally called Lambert’s W function and denoted by \eta=W(x) . This function is not very common, but it is present in most numerical and symbolic libraries. The expression for Bell numbers obtained by Moser and Wyman ( 10 ) reads: (2) B_{n}\approx B_{n}^{\ast}=\frac{e^{nW(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). While this is an asymptotic expression for B_{n} , remarkably, it gives a very good approximation for all values of n . Specifically, comparing the result from Eq. 2 with the exact values numerically, we found that the relative difference |B^{\ast}_{n}-B_{n}|/B_{n} is smaller than 3\cdot 10^{-3} for all 2\leq n\leq 50 . Moreover, for n=1\ldots 7 , the integer part of B_{n}^{\ast} is exactly equal to B_{n} . Berend and Tassa ( 1 ) proved the following upper bound on Bell numbers: (3) B_{n}<\overline{B}_{n}=\left(\frac{0.792\,n}{\log(n+1)}\right)^{n}, valid for any n . Comparisons show that this bound is very tight for small n , and becomes less good for larger n . (For n\leq 8 it deviates by up to 15\% , and for n=20 it overestimates the exact value by a factor of 4.) The formula for \overline{B}_{n} is much simpler than Eq. 2 and can be used to estimate Bell numbers for n not too large. 4. Algorithms for listing set partitions Finding the optimal arrangement of objects requires, as discussed above, in some cases a listing of all partitions of a set. The problem of finding an efficient algorithm for enumerating set partitions was repeatedly treated in the literature. However, a comparison of the different proposals, with an eye towards practical use, is lacking. The recursion of Eq. 1 and similar ones suggest that the problem of generation of all set partitions can be solved recursively. While this is true, recursive algorithms in practice are less efficient than non-recursive (iterative) ones. The main reason is that repeated function calling creates an overhead which is also very much system- and compiler-specific. It is clear that, generally, iterative algorithms outperform recursive ones. Thus we only benchmark the non-recursive algorithms. A class of algorithms for generating set partitions is based on