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 , 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,

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

The intersection  of sets S and T is written . The elements of 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. E.g., if and , the intersection is .

The difference  of sets S and T, written S-T, contains those elements of S which are not also elements of T. I.e., the result S-T is obtained by taking the set S and removing from it those elements which are also found in T.

Program  gives the implementations of the union, intersection, and difference operators (+, *, and -, respectively) for operands of type MultisetAsArray. This code is quite similar to that of the SetAsArray class (Program ) and the SetAsBitVector class (Program ). The worst-case running time of each of these operations is O(N).

  
Program: MultisetAsArray Class Union, Intersection and Difference Operator Definitions

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

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