Parallel Algorithms for Generating Integer Partitions and Compositions

We present cost-optimal parallel algorithms for generating partitions and compositions of an integer \(n\) in lexicographic order. The algorithms utilize a linear array of \(n\) processors, where each processor has constant-size memory and is responsible for producing one part of a given partition or composition.