Algorithms for generating integer partitions.

Description
Title: Algorithms for generating integer partitions.
Authors: Zoghbi, Antoine C.
Date: 1993
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.
URL: http://hdl.handle.net/10393/6506
http://dx.doi.org/10.20381/ruor-11312
CollectionTh├Ęses, 1910 - 2010 // Theses, 1910 - 2010
Files
MM89677.PDF1.83 MBAdobe PDFOpen