Simple constant amortized time generation of fixed length numeric partitions

摘要

A numeric partition of n of fixed length k is an unordered sequence of k positive integers that sum to n. A recent implementation of Savage's constant amortized time (CAT) algorithm for generating numeric partitions in a minimal change order required over twenty-five pages of C code. According to Ruskey, there is no simple lexicographic algorithm that generates fixed length numeric partitions in the natural representation in constant amortized time (CAT) per partition. This paper describes such an algorithm and proves it is a CAT algorithm. As a byproduct. CAT generators are given for several other classes of numerical partitions, some of which have no prior CAT algorithm. (C) 2004 Elsevier Inc. All rights reserved.