Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Array and Bit-Vector Sets

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 abstract Set class defined in Program . This class uses an array of length to represent the elements of where .

program27690
Program: SetAsArray class __init__ method.

Program defines the __init__ method for the SetAsArray class. In addition to self, the __init__ method takes a single argument , which defines the universe and, consequently, the size of the array of bool values. The __init__ method creates the empty set by initializing all the elements of the bool array to False. Clearly, the running time of the __init__ method is O(N), where .