Parallel generation of permutations and combinations (Q1085616)

In this paper we present a parallel algorithm to generate the permutations of at most k out of n objects. The architecture consists of a linear processor array and a selector. When one single processor array is available, a parallel algorithm to generate permutations is presented wich achieves the best possible speedup for any given k. Also, this algorithm can easily be modified to generate combinations. When multiple processor arrays are available, a parallel scheme is proposed to speed up the generation by fully utilizing these processor arrays. The degree of parallelism is related to the number of available processor arrays.