The parallel generation of combinations.

The parallel generation of combinations.

Show full item record

Title: The parallel generation of combinations.
Author: Elhage, Hassan.
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 cost-optimal, 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.
Date: 1995
URI: http://hdl.handle.net/10393/10041

Files in this item

Files Size Format View
MM11553.PDF 2.196Mb application/pdf View/Open

This item appears in the following Collection(s)

Show full item record


Contact information

Morisset Hall (map)
65 University Private
Ottawa ON Canada
K1N 6N5

Tel. 613-562-5800 (4563)
Fax 613-562-5195

ruor@uottawa.ca