A NEW METHOD FOR GENERATING INTEGER COMPOSITIONS IN PARALLEL
Hong Shen, David John Evans · International Journal of Parallel Emergent and Distributed Systems · 1996
A novel method, binary countdown transformation, for generating integer compositions in parallel is proposed. Based on this method, an optimal and highly adaptive parallel algorithm for generating all compositions of integer n is presented. The algorithm runs on p processors on a simple SIMD model requiring neither shared memory nor interconnection network and has a worst-case time complexity of O(n2 n−1/p), 1 ≤ p ≤ 2 n−1. All the compositions generated are in lexicographic order. The proposed algorithm is superior to those built on generating combinations and set partitions.