Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |

In this section we consider finite sets over a finite universe.
Specifically, the universe we consider is ,
the set of integers in the range from zero to *N*-1,
for some fixed and relatively small value of *N*.

Let be the universe.
Every set which we wish to represent is a subset of *U*.
The set of all subsets of *U* is called the *power set*
of *U* and is written .
Thus, the sets which we wish to represent are the *elements* of .
The number of elements in the set *U*, written |*U*|, is *N*.
Similarly, .
This observation should be obvious:
For each element of the universal set *U* there are only two possibilities:
Either it is, or it is not,
a member of the given set.

This suggests a relatively straightforward
representation of the elements of --an array of `bool` values, one for each element of the universal set.
By using array subscripts in *U*,
we can represent the set implicitly.
That is, *i* is a member of the set if the array element
is true.

Program introduces the class `SetAsArray`.
The `SetAsArray` class extends the `AbstractSet` class
defined in Program .
This class uses an array of length
to represent the elements of where .

Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.