A Fast Algorithm for Generating Set Partitions

M. C. Er

The Computer Journal · 1988 · 37 citations · 0 references

DOIFull text

Open access

Concepts

Abstract

A recursive algorithm for generating all partitions of the set {1, 2, …, n} is presented. The average time complexity per partition generated of this algorithm is 𝛉(1.6). This algorithm runs faster than the previously fastest algorithm, whose average time complexity per partition is 𝛉(4). An empirical test confirms that this is indeed the case.