DOI: 10.11648/j.ajcst.20260903.12 ISSN: 2640-012X

Methods for Counting and Enumerating Set Partitions

Arnav Khinvasara, Alexander Pikovski
Show PDF Cite
Set partitions are arrangements of distinct objects into groups. After a brief review of the subject, we consider the task of counting and enumerating set partitions. The number of set partitions, known as Bell number, is a rapidly increasing number and does not have an explicit formula. We study approximate expressions for the Bell number given in the literature. We find that an asymptotic formula of Moser and Wyman gives a surprisingly accurate approximation to the Bell number even for small set sizes. Furthermore, a simple expression due to Berend and Tasssa can be conveniently used to approximate the Bell number for small set sizes. % Next, we consider enumeration of set partitions. The problem of listing all set partitions arises in a variety of settings, in particular in combinatorial optimization tasks. Algorithms for enumerating all set partitions are reviewed. The focus is on non-recursive algorithms without Gray code constructions. We compare the classic algorithm of Hutchinson with three more modern ones. Empirically, it is found that all of them scale exponentially with the set size. While the exact compiler and optimization settings do matter, it can be concluded that the algorithm of Djokic et al. is the fastest one, thus it is recommended for practical use.

More from our Archive