Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Comparing Sets

There is a special family of operators for comparing sets. Consider two sets, say S and T. We say that S is a subset  of T, written tex2html_wrap_inline62517, if every element of S is also an element of T. If there is at least one element of T that is not also an element of S, we say that S is a proper subset   of T, written tex2html_wrap_inline66517. We can also reverse the order in which the expressions are written to get tex2html_wrap_inline66519 or tex2html_wrap_inline66521, which indicates that T is a (proper) superset    of S.

The set comparison operators follow the rule that if tex2html_wrap_inline62517 and tex2html_wrap_inline62519 then tex2html_wrap_inline66531, which is analogous to a similar property of numbers: tex2html_wrap_inline66533. However, set comparison is unlike numeric comparison in that there exist sets S and T for which neither tex2html_wrap_inline62517 nor tex2html_wrap_inline62519! For example, clearly this is the case for tex2html_wrap_inline66543 and tex2html_wrap_inline66545. Mathematically, the relation tex2html_wrap_inline66547 is called a partial order  because there exist some pairs of sets for which neither tex2html_wrap_inline62517 nor tex2html_wrap_inline62519 holds; whereas the relation tex2html_wrap_inline59071 (among integers, say) is a total order.

Program gif defines the methods Equals and IsSubset each of which take argument that is assumed to be a SetAsArray instance. The former tests for equality and the latter determines whether the relation tex2html_wrap_inline66547 holds between this and set. Both operators return a bool result. The worst-case running time of each of these operations is clearly O(N).

   program27755
Program: SetAsArray class Equals and IsSubset methods.

A complete repertoire of comparison methods would also include methods to compute tex2html_wrap_inline66559, tex2html_wrap_inline66561, tex2html_wrap_inline66563, and tex2html_wrap_inline60913. These operations follow directly from the implementation shown in Program gif (Exercise gif).


next up previous contents index

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