Problem: Set Operations

Every operation in the Set chapter works on a single element: add one, remove one, ask about one. But often we want to combine two whole sets. Given the set of students enrolled in one course and the set enrolled in another, we might want the students in either course, or only the students in both, or the students in the first course but not the second. These are the three standard operations from set theory.

For two sets $A$ and $B$ :

The union $A \cup B$ is the set of elements in $A$ or in $B$ (or in both).
The intersection $A \cap B$ is the set of elements in both $A$ and $B$ .
The difference $A - B$ is the set of elements in $A$ but not in $B$ .

Let $A = {1, 2, 3, 4}$ and $B = {3, 4, 5}$ :

$A \cup B = {1, 2, 3, 4, 5}$
$A \cap B = {3, 4}$
$A - B = {1, 2}$

Each operation produces a new set and does not change $A$ or $B$ . Difference is the only one where it matters which set comes first: $B - A = {5}$ , which is not the same as $A - B$ .

We would like to write these as code that takes two Set objects. We cannot do that yet. Our Set interface offers only add, remove, contains, and size, and none of them returns the elements one at a time. So code that holds a set has no way to visit every element of it. The next chapter fixes that. For now, we work on arrays.

We represent each set as an int array with no duplicate values. An unsorted array holds its values the way ArraySet holds its elements. LinkedSet keeps its elements in nodes, but it also keeps them in no particular order and finds one by scanning, so what we work out for the unsorted array applies to it too. A sorted array holds its values the way SortedArraySet does.

The signatures of the methods in Java might look like this:

public static int[] union(int[] arr1, int[] arr2)
public static int[] intersection(int[] arr1, int[] arr2)
public static int[] difference(int[] arr1, int[] arr2)

public static int[] sortedIntersection(int[] arr1, int[] arr2)
public static int[] sortedDifference(int[] arr1, int[] arr2)

Here arr1 holds $A$ and arr2 holds $B$ . No method changes its inputs.

There is no sortedUnion in the list. The union of two sorted arrays was a practice problem in the merge sort chapter. Its solution is the merge with one change: when the two values are equal, it copies the value once and advances both pointers.

A set has no order, so the values of a result could come out in any order. To make the results easy to check, we fix the order. The union has the values of arr1 in their order, followed by the values of arr2 that are not in arr1, in their order. The intersection and the difference keep their values in the order they have in arr1. For the sorted methods, the result is sorted.