Fast algorithms for genegrating integer partitions

Abstract

We present two new algorithms for generating integer partitions in the standard representation. They generate partitions in lexicographic and anti-lexicographic order, respectively. We prove that both algorithm generate partitions with constant average delay, exclusive of the output. These are the first known algorithms to produce partitions in the standard representation and with constant average delay. The performance of all known integer partition algorithms-is measured and compared, separately for the standard and multiplicity representation. An empirical test shows that both new algorithms are several times faster than any of previously known algorithms for generating unrestricted integer partitions in the standard representation. Moreover, they are faster than any known algorithm for generating integer partition in the multiplicity representation (exclusive of the output).

Keywords:

• Combinatorial objects
• lexicographic order
• integer partitions

C.R. Categories::

• G.2.1. Combinational algorithms, integer partitions