Constant Time Generation of Set Partitions

Shin-ichiro KAWANO, Shin-ichi NAKANO

Summary :

In this paper we give a simple algorithm to generate all partitions of {1,2,,n} into k non-empty subsets. The number of such partitions is known as the Stirling number of the second kind. The algorithm generates each partition in constant time without repetition. By choosing k = 1,2,,n we can also generate all partitions of {1,2,,n} into subsets. The number of such partitions is known as the Bell number.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.4 pp.930-934
• Publication Date: 2005/04/01
• DOI: 10.1093/ietfec/e88-a.4.930
• Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)

Authors

Shin-ichiro KAWANO
Shin-ichi NAKANO

Keyword

algorithm,  enumeration,  the Stirling number of the second kind,  the Bell number,  Gray code