Parallel generation of permutations and combinations (Q1085616)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Parallel generation of permutations and combinations
scientific article

    Statements

    Parallel generation of permutations and combinations (English)
    0 references
    0 references
    0 references
    0 references
    1986
    0 references
    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.
    0 references
    0 references
    parallel algorithm
    0 references
    degree of parallelism
    0 references