Constant Time Generation of Set Partitions

摘要

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.