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

Sets, Multisets, and Partitions

 

In mathematics a set  is a collection of elements, especially a collection having some feature or features in common. The set may have a finite number of elements, e.g., the set of prime numbers less than 100; or it may have an infinite number of elements, e.g., the set of right triangles. The elements  of a set may be anything at all--from simple integers to arbitrarily complex objects. However, all the elements of a set are distinct--a set may contain only one instance of a given element.

For example, tex2html_wrap_inline65986, tex2html_wrap_inline65988, tex2html_wrap_inline65990, and tex2html_wrap_inline65992 are all sets the elements of which are drawn from tex2html_wrap_inline65994. The set of all possible elements, U, is called the universal set . Note also that the elements comprising a given set are not ordered. Thus, tex2html_wrap_inline65998 and tex2html_wrap_inline66000 are the same set.

There are many possible operations on sets. In this chapter we consider the most common operations for combining sets--union, intersection, difference:

union
The union  (or conjunction ) of sets S and T, written tex2html_wrap_inline66006, is the set comprised of all the elements of S together with all the elements of T. Since a set cannot contain duplicates, if the same item is an element of both S and T, only one instance of that item appears in tex2html_wrap_inline66006. If tex2html_wrap_inline66018 and tex2html_wrap_inline66020, then tex2html_wrap_inline66022.
intersection
The intersection  (or disjunction ) of sets S and T is written tex2html_wrap_inline66028. The elements of tex2html_wrap_inline66028 are those items which are elements of both S and T. If tex2html_wrap_inline66018 and tex2html_wrap_inline66020, then tex2html_wrap_inline66040.
difference
The difference  (or subtraction ) of sets S and T, written S-T, contains those elements of S which are not also elements of T. That is, the result S-T is obtained by taking the set S and removing from it those elements which are also found in T. If tex2html_wrap_inline66018 and tex2html_wrap_inline66020, then tex2html_wrap_inline66062.

Figure gif illustrates the basic set operations using a Venn diagram . A Venn diagram represents the membership of sets by regions of the plane. In Figure gif the two sets S and T divide the plane into the four regions labeled I-IV. The following table illustrates the basic set operations by enumerating the regions that comprise each set.

   figure27273
Figure: Venn diagram illustrating the basic set operations.

set region(s) of Figure gif
U I, II, III, IV
S I, II
S' III, IV
T II, III
tex2html_wrap_inline66006 I, II, III
tex2html_wrap_inline66028 II
S-T I
T-S III




next up previous contents index

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