Algorithms for generating integer partitions.

Abstract

In this thesis we consider the problem of generating integer partitions. We provide an overview of all known algorithms for the sequential generation of partitions of an integer. The performance is measured and compared separately for the standard and multiplicity representation of integer partitions. We present two new algorithms for generating integer partitions in the standard representation which generate partitions in lexicographic and antilexicographic order respectively. We prove that both algorithms generate partitions with constant average delay (exclusive of the output; output is generated and not printed). Historically, all existing algorithms for generating integer partitions in the multiplicity representation showed better performance than all the existing algorithms for generating integer partitions in the standard representation. An empirical test shows that both new algorithms are a few times faster than any previously known algorithms for generating unrestricted integer partitions in the standard representation. Moreover, they are faster than any known algorithm for generating integer partitions in the multiplicity representation (exclusive of the output). We describe several modifications to existing algorithms, and a transformation of one algorithm from the standard to the multiplicity representation. Finally, we provide a brief overview of sequential and parallel algorithms that generate partitions at random, and an analysis of a parallel algorithm for generating all partitions.