Database Reference
In-Depth Information
NOTE
This topic uses some basic mathematic terms and formulas. If your
math skills are rusty and you find these concepts a little challenging, a
helpful resource is
A First Course in Probability
by Sheldon Ross.
Sets can be combined in three basic ways. The
union
of a set, written A
∪
B,
is the set that contains all of the elements in A and all of the elements in
B. The
intersection
of a set, written AB, is the set the contains all of the
elements in A that are also elements of B. Finally, the
complement
of the set,
written “A \ B”, is the set that contains elements of set A that are
not
in set
B.
In Java, the basic union, intersection and complement methods are
addAll()
,
retainAll()
, and
removeAll()
, respectively. These
primitive methods can be used to implement union and intersection for an
arbitrary number of sets as follows:
public static Set<E> union(Set<E>...sets) {
Set<E> union = new Set<E>();
for(Set<E> s : sets) union.addAll(s);
return union;
}
public static Set<E> intersection(Set<E>...sets) {
Set<E> intersection = new Set<E>();
intersection.addAll(sets[0]);
for(int i=1;i<sets.length;i++)
intersection.retainAll(sets[i]);
return intersection;
}
The number of elements in a set is called the
cardinality
of the set. It is
denoted by enclosing the set in | symbols. For example, the cardinality of
the set A is written as |A|. In Java, the
size()
method returns the basic set
cardinality.
Computing thecardinality ofthesetunionorintersection issomewhatmore
interesting. In most of the algorithms given later in this chapter, computing