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

Union, Intersection, and Difference

Because multisets permit duplicates but sets do not, the definitions of union, intersection, and difference are slightly modified for multisets. The union  of multisets S and T, written tex2html_wrap_inline66006, is the multiset comprised of all the elements of S together with all the element of T. Since a multiset may contain duplicates, it does not matter if the same element appears in S and T.

The subtle difference between union of sets and union of multisets gives rise to an interesting and useful property. If S and T are regular sets,

displaymath66326

On the other hand, if S and T are multisets,

displaymath66327

The intersection  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 a given element appears more than once in S or T (or both), the intersection contains m copies of that element, where m is the smaller of the number of times the element appears in S or T. For example, if tex2html_wrap_inline66376 and tex2html_wrap_inline66378, the intersection is tex2html_wrap_inline66380.

The difference  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.

Program gif gives the implementations of the union, intersection, and difference methods of MultisetAsArray class. This code is quite similar to that of the SetAsArray class (Program gif) and the SetAsBitVector class (Program gif). The worst-case running time of each of these operations is O(N).

   program27722
Program: MultisetAsArray class union, intersection and difference methods.

Instead of using the boolean operators &&, ||, and !, we have used + (integer addition), Math.min and - (integer subtraction). The following table summarizes the operators used in the various set and multiset implementations.

class

operation

SetAsArray SetAsBitVector MultisetAsArray
union || | +
intersection && & Math.min
difference && and ! & and <= and -


next up previous contents index

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