Given n objects, (1,2, . . . ,n), and m≤9Tn processors connected in a logical ring, an algorithm is given for generating permutations of length k ≤9Tm or less. It is shown that the quotient of the sequential and parallel time complexities is O(m). Thus, a maximum speedup is attained. A divide-and-conquer approach is used where the responsibility for generating specific subsets of permutations is meted out based on the value of the leading object. Responsibility for subsequences is assigned in the same way, and such subsequences are shared by shifting components (with modification) around the ring. The authors show how to extend the algorithm from rings to arrays of processors.

This paper would be of interest to someone in search of a concise example of the divide-and-conquer paradigm. It might be of interest to those seeking parallel heuristic solutions to the knapsack or other combinatorial programming problems. While the text is complicated by the use of nonstandard phrases that describe standard algorithmic steps (e.g., the manipulation of stacks), an excellent example is presented that dissolves the ambiguity.