Abstract:

In this thesis we consider the problem of the generation of combinations of m elements chosen from a set of n elements. We provide a survey of the sequential and parallel algorithms for the generation of the (m,n)combinations. The major achievement of this thesis is a parallel algorithm for generating all combinations without repetitions of m elements from an arbitrary set of n elements in loxicographic ascending order. The algorithm uses a linear systolic array of m processors, each having constant size memory (except processor m, which has O(n) memory), and each being responsible for producing one element of a given combination. There is a constant delay between successive combinations, leading to an O(c(m,n)) time solutions, where C(m,n) is the total number of (m,n)combinations. The algorithm is costoptimal, assuming the time to output the combination is counted, and does not deal with very large integers. This algorithm is an improvement over all previous works because it generates combinations of a set of arbitrary elements $\{p\sb1,\ p\sb2,\... ,\ p\sb{n}\}$, on which an order relation is defined such that $p\sb1p\sb2\... p\sb{n}$. This property is important since it allows us to distinguish between algorithms that generate combinations of any ordered set, and algorithms that can only generate combinations of the set $\{$1, 2,$\... ,\ n\}$. Last, we modify this algorithm to generate combinations with repetitions in lexicographic order chosen from a set of arbitrary objects. 