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.
| Published in | American Journal of Computer Science and Technology (Volume 9, Issue 3) |
| DOI | 10.11648/j.ajcst.20260903.12 |
| Page(s) | 115-119 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2026. Published by Science Publishing Group |
Set Partitions, Bell Numbers, Algorithms, Benchmarking, Optimization
| [1] | J. T. Butler and T. Sasao, "High-speed hardware partition generation," ACM Trans. Reconfigurable Technol. Syst., vol. 7, Dec. 2014. |
| [2] | R. K. Hankin and L. J. West, "Set partitions in R," Journal of Statistical Software, vol. 23, pp. 1–12, 2008. |
| [3] | G.-C. Rota, "The number of partitions of a set," The American Mathematical Monthly, vol. 71, no. 5, pp. 498–504, 1964. |
| [4] | M. Z. Spivey, "A generalized recurrence for Bell numbers," J. Integer Seq., vol. 11, no. 08.2, p. 5, 2008. |
| [5] | D. E. Knuth, Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Boston: Addison-Wesley, 2011. |
| [6] | T. Mansour, Combinatorics of set partitions. Boca Raton: CRC Press, 2013. |
| [7] | J. Grunwald and G. Serafin, "Explicit bounds for Bell numbers and their ratios," Journal of Mathematical Analysis and Applications, vol. 549, no. 2, p. 129527, 2025. |
| [8] | L. Moser and M.Wyman, "An asymptotic formula for the Bell numbers," Trans. Roy. Soc. Can., vol. 49, no. Series III, Sec. III, pp. 49–54, 1955. |
| [9] | D. Berend and T. Tassa, "Improved bounds on Bell numbers and on moments of sums of random variables," Probability and Mathematical Statistics, vol. 30, no. 2, pp. 185–205, 2010. |
| [10] | S. Kawano and S. Nakano, "Constant time generation of set partitions," IEICE Transactions on Fundamentals, vol. E88-A, pp. 930–934, April 2005. |
| [11] | G. Hutchinson, "Partioning algorithms for finite sets," Communications of the ACM, vol. 6, no. 10, pp. 613–614, 1963. |
| [12] | I. Semba, "An efficient algorithm for generating all partitions of the set 1, 2,..., n," Journal of Information Processing, vol. 7, no. 1, pp. 41–42, 1984. |
| [13] | M. Er, "A fast algorithm for generating set partitions," The Computer Journal, vol. 31, no. 3, pp. 283–284, 1988. |
| [14] | B. Djoki'c, M. Miyakawa, S. Sekiguchi, I. Semba, and I. Stojmenovi'c, "A fast iterative algorithm for generating set partitions," The Computer Journal, vol. 32, no. 3, pp. 281-82, 1989. |
| [15] | G. Stamatelatos and P. S. Efraimidis, "Lexicographic enumeration of set partitions." arXiv preprint 2105.07472, |
APA Style
Khinvasara, A., Pikovski, A. (2026). Methods for Counting and Enumerating Set Partitions. American Journal of Computer Science and Technology, 9(3), 115-119. https://doi.org/10.11648/j.ajcst.20260903.12
ACS Style
Khinvasara, A.; Pikovski, A. Methods for Counting and Enumerating Set Partitions. Am. J. Comput. Sci. Technol. 2026, 9(3), 115-119. doi: 10.11648/j.ajcst.20260903.12
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.ajcst.20260903.12,
author = {Arnav Khinvasara and Alexander Pikovski},
title = {Methods for Counting and Enumerating Set Partitions},
journal = {American Journal of Computer Science and Technology},
volume = {9},
number = {3},
pages = {115-119},
doi = {10.11648/j.ajcst.20260903.12},
url = {https://doi.org/10.11648/j.ajcst.20260903.12},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajcst.20260903.12},
abstract = {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.},
year = {2026}
}
TY - JOUR T1 - Methods for Counting and Enumerating Set Partitions AU - Arnav Khinvasara AU - Alexander Pikovski Y1 - 2026/09/23 PY - 2026 N1 - https://doi.org/10.11648/j.ajcst.20260903.12 DO - 10.11648/j.ajcst.20260903.12 T2 - American Journal of Computer Science and Technology JF - American Journal of Computer Science and Technology JO - American Journal of Computer Science and Technology SP - 115 EP - 119 PB - Science Publishing Group SN - 2640-012X UR - https://doi.org/10.11648/j.ajcst.20260903.12 AB - 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. VL - 9 IS - 3 ER -
Research and Development, Unatech GmbH, Berlin, Germany
Information