Generating All Partitions: A Comparison Of Two Encodings

Abstract

Integer partitions may be encoded as either ascending or descending compositions for the purposes of systematic generation. Many algorithms exist to generate all descending compositions, yet none have previously been published to generate all ascending compositions. We develop three new algorithms to generate all ascending compositions and compare these with descending composition generators from the literature. We analyse the new algorithms and provide new and more precise analyses for the descending composition generators. In each case, the ascending composition generation algorithm is substantially more efficient than its descending composition counterpart. We develop a new formula for the partition function p(n) as part of our analysis of the lexicographic succession rule for ascending compositions.

40 pages, 2 figures. Derived from J. Kelleher's Ph.D thesis, Encoding Partitions as Ascending Compositions, University College Cork, 2006. V2: corrected typos in RuleDesc algorithm

References in corpus (3)

• On the Quantum Density of States and Partitioning an Integer
• Quantum $1/f$ Noise in Equilibrium: from Planck to Ramanujan
• Calculation of the number of partitions with constraints on the fragment size

Cited by in corpus (6)

• Fast algorithm for generating ascending compositions
• Developments from Programming the Partition Method for a Power Series Expansion
• Fundamental Limits of Stochastic Shared Caches Networks
• Approximation of the Partition Number After Hardy and Ramanujan: An Application of Data Fitting Method in Combinatorics
• Selection and Coalescence in a Finite State Model
• Subset-lex: did we miss an order?