On Parallel Generation of Combinations in Associative Processor Architectures.
Zbigniew Kokosiński · 1997
In this paper two new parallel algorithms are presented for generation of (n,k)-combinations. Computations run in associative processor models. Objects are generated in lexicographic order, with O(1) time per object, in two different representations. The first algorithm uses the conventional representation of combinations while the second algorithm generates combinations in the form of binary vectors and therefore is particularly well suited for row/column masks generation in associative processors. The algorithms may be also used for generation of related combinatorial objects like combinations with repetitions and integer compositions. Keywords: choice function, combination generation, associative processing. 1. INTRODUCTION The first known algorithm for generating (n,k)- combinations published in 1960 is due to Lehmer [27]. In the following years a number of sequential algorithms was developed [7, 9, 26, 33, 38, 40, 41]. Sequential generation methods were reviewed and compared tw...