Constant Time Generation of Set Partitions

Shin-ichiro KAWANO  Shin-ichi NAKANO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.4   pp.930-934
Publication Date: 2005/04/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.4.930
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
algorithm,  enumeration,  the Stirling number of the second kind,  the Bell number,  Gray code,  

Full Text: PDF(232.4KB)>>
Buy this Article




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.