Algorithm Z1 Accelerated and Parallel Generation of Integer Partitions in Standard Representation Form —Improving the Fastest Existing Algorithm ZS1

Abstract

Algorithm ZS1, which generates integer partitions in standard representation and anti-lexicographic order, was first introduced in Mr. Zoghbi’s Master’s thesis, “ Algorithms for Generating Integer Partitions ” (University of Ottawa, 1993), and later published in “ Fast Algorithms for Generating Integer Partitions ” by Zoghbi and Stojmenovi? (International Journal of Computer Mathematics, 1998, Vol. 70, pp. 319-332). The algorithm is widely regarded by specialists as one of the most efficient methods for generating integer partitions. Algorithm Z1 is an optimized refinement of ZS1. Experimental results demonstrate that Z1 achieves up to 36% reduction in execution time compared with ZS1 in single-threaded environments. In addition, multi-threaded implementations of both ZS1 and Z1 attain runtime reductions up to an 89% relative to their sequential counterparts, highlighting the significant impact of compiler optimizations and system architecture on overall performance.