Mahozad
Mahozad

Reputation: 24790

Union or intersection of Java Sets

What is the simplest way to make a union or an intersection of Sets in Java? I've seen some strange solutions to this simple problem (e.g. manually iterating the two sets).

Union/Intersection of Java sets

Upvotes: 58

Views: 101962

Answers (7)

Donald Raab
Donald Raab

Reputation: 6706

If you are using or are open to using Eclipse Collections, then the following will work with both mutable and immutable varieties of object and primitive sets. I am using ImmutableSet and ImmutableIntSet in the examples to show that neither of the Set instances are mutated as a result of the operations.

Here is an example of union and intersect with two instances of ImmutableSet<String>.

@Test
public void objectSets()
{
    ImmutableSet<String> one = Sets.immutable.with("🍎", "🍌", "🍐");
    ImmutableSet<String> two = Sets.immutable.with("🍎", "🍒", "🍌");

    ImmutableSet<String> union = one.union(two);
    Assertions.assertEquals(Set.of("🍎", "🍌", "🍐", "🍒"), union);

    ImmutableSet<String> intersection = one.intersect(two);
    Assertions.assertEquals(Set.of("🍎", "🍌"), intersection);
}

Here is an example of union and intersect with two instances of ImmutableIntSet.

@Test
public void primitiveSets()
{
    ImmutableIntSet one = IntSets.immutable.with(1, 2, 3);
    ImmutableIntSet two = IntSets.immutable.with(1, 4, 2);

    ImmutableIntSet union = one.union(two);
    Assertions.assertEquals(IntSets.immutable.with(1, 2, 3, 4), union);

    ImmutableIntSet intersection = one.intersect(two);
    Assertions.assertEquals(IntSets.immutable.with(1, 2), intersection);
}

Eclipse Collections has support for union and intersect as well as difference, symmetricDifference, cartesianProduct for all object Set and primitive Sets. All eight Java primitive types are supported with primitive Sets.

There is a two part blog series with more information about the operations available on primitive sets. Part 1 and Part 2.

Note: I am a committer for Eclipse Collections.

Upvotes: 1

Subfire
Subfire

Reputation: 97

mutable:
    java.util.AbstractCollection#retainAll      # intersection
    java.util.AbstractCollection#addAll         # union
    java.util.AbstractCollection#removeAll      # difference

immutable: Stream
    Set<Integer> intersection = set1.stream()   # intersection
            .filter(set2::contains)
            .collect(Collectors.toSet());
    Set<Integer> union = Stream.concat(set1.stream(), set2.stream())    # union
            .collect(Collectors.toSet());
    Set<Integer> difference = set1.stream()     # difference
            .filter(e -> !set2.contains(e))
            .collect(Collectors.toSet());

immutable: Apache Commons Collections
    org.apache.commons.collections4.SetUtils#union
    org.apache.commons.collections4.ListUtils#union
    org.apache.commons.collections4.SetUtils#disjunction
    org.apache.commons.collections4.SetUtils#difference

immutable: Guava Collections
    Sets.intersection(set1, set2);      # intersection
    Sets.union(set1, set2);             # union
    Sets.difference(set1, set2);        # difference

Upvotes: 0

Sam Ginrich
Sam Ginrich

Reputation: 851

When I think of union and intersection, it is in the first loop an operation on sets, i.e. a map
            Set<T>  x  Set<T>  →  Set<T>
Not clear, why it would appear in Java design that shirtsleeved.

static <T> Set<T> union(Set<T> a, Set<T> b)
{
    Set<T> res = new HashSet<T>(a);
    res.addAll(b);
    return res;
}

static <T> Set<T> intersection(Set<T> a, Set<T> b)
{
    Set<T> res = new HashSet<T>(a);
    res.retainAll(b);
    return res;
}

Upvotes: 0

VamVag
VamVag

Reputation: 9

    import java.util.*;

public class sets {
    public static void swap(int array[], int a, int b) { // Swap function for sorting
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static int[] sort(int array[]) { // sort function for binary search (Selection sort)
        int minIndex;
        int j;
        for (int i = 0; i < array.length; i++) {
            minIndex = i;
            for (j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j])
                    minIndex = j;
            }
            swap(array, minIndex, i);
        }
        return array;
    }

    public static boolean search(int array[], int search) { // Binary search for intersection and difference
        int l = array.length;
        int mid = 0;
        int lowerLimit = 0, upperLimit = l - 1;
        while (lowerLimit <= upperLimit) {
            mid = (lowerLimit + upperLimit) / 2;
            if (array[mid] == search) {
                return true;
            } else if (array[mid] > search)
                upperLimit = mid - 1;
            else if (array[mid] < search)
                lowerLimit = mid + 1;
        }
        return false;
    }

    public static int[] append(int array[], int add) { // To add elements
        int newArray[] = new int[array.length + 1];
        for (int i = 0; i < array.length; i++) {
            newArray[i] = array[i];
        }
        newArray[array.length] = add;
        newArray = sort(newArray);
        return newArray;
    }

    public static int[] remove(int array[], int index) { // To remove duplicates
        int anotherArray[] = new int[array.length - 1];
        int k = 0;
        if (array == null || index < 0 || index > array.length) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            if (index == i) {
                continue;
            }
            anotherArray[k++] = array[i];
        }
        return anotherArray;
    }

    public static void Union(int A[], int B[]) { // Union of a set
        int union[] = new int[A.length + B.length];
        for (int i = 0; i < A.length; i++) {
            union[i] = A[i];
        }
        for (int j = A.length, i = 0; i < B.length || j < union.length; i++, j++) {
            union[j] = B[i];
        }
        for (int i = 0; i < union.length; i++) {
            for (int j = 0; j < union.length; j++) {
                if (union[i] == union[j] && j != i) {
                    union = remove(union, j); // Removing duplicates
                }
            }
        }
        union = sort(union);
        System.out.print("A U B = {"); // Printing
        for (int i = 0; i < union.length; i++) {
            if (i != union.length - 1)
                System.out.print(union[i] + ", ");
            else
                System.out.print(union[i] + "}");
        }
    }

    public static void Intersection(int A[], int B[]) {
        int greater = (A.length > B.length) ? (A.length) : (B.length);
        int intersect[] = new int[1];
        int G[] = (A.length > B.length) ? A : B;
        int L[] = (A.length < B.length) ? A : B;
        for (int i = 0; i < greater; i++) {
            if (search(L, G[i]) == true) { // Common elements
                intersect = append(intersect, G[i]);
            }
        }
        for (int i = 0; i < intersect.length; i++) {
            for (int j = 0; j < intersect.length; j++) {
                if (intersect[i] == intersect[j] && j != i) {
                    intersect = remove(intersect, j); // Removing duplicates
                }
            }
        }
        System.out.print("A ∩ B = {"); // Printing
        for (int i = 1; i < intersect.length; i++) {
            if (i != intersect.length - 1)
                System.out.print(intersect[i] + ", ");
            else
                System.out.print(intersect[i] + "}");
        }
    }

    public static void difference(int A[], int B[]) {
        int diff[] = new int[1];
        int G[] = (A.length > B.length) ? A : B;
        int L[] = (A.length < B.length) ? A : B;
        int greater = G.length;
        for (int i = 0; i < greater; i++) {
            if (search(L, G[i]) == false) {
                diff = append(diff, G[i]); // Elements not in common
            }
        }
        for (int i = 0; i < diff.length; i++) {
            for (int j = 0; j < diff.length; j++) {
                if (diff[i] == diff[j] && j != i) {
                    diff = remove(diff, j); // Removing duplicates
                }
            }
        }
        System.out.println("Where A is the larger set, and B is the smaller set.");
        System.out.print("A - B = {"); // Printing
        for (int i = 1; i < diff.length; i++) {
            if (i != diff.length - 1)
                System.out.print(diff[i] + ", ");
            else
                System.out.print(diff[i] + "}");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the operation");
        String operation = sc.next().toLowerCase();
        System.out.println("Enter the length of the first set.");
        int l1 = sc.nextInt();
        System.out.println("Enter the length of the second set.");
        int l2 = sc.nextInt();
        int A[] = new int[l1];
        int B[] = new int[l2];
        System.out.println("Enter the elements of the first set.");
        System.out.print("A = ");
        for (int i = 0; i < l1; i++) {
            A[i] = sc.nextInt();
        }
        System.out.println("Enter the elements of the second set.");
        System.out.print("B = ");
        for (int i = 0; i < l2; i++) {
            B[i] = sc.nextInt();
        }
        A = sort(A); // Sorting the sets before passing
        B = sort(B);
        sc.close();
        switch (operation) {
            case "union":
                Union(A, B);
                break;
            case "intersection":
                Intersection(A, B);
                break;
            case "difference":
                difference(B, A);
                break;
            default:
                System.out.println("Invalid Operation");
        }
    }
}

Upvotes: 0

Mahozad
Mahozad

Reputation: 24790

The simplest one-line solution is this:

set1.addAll(set2); // Union
set1.retainAll(set2); // Intersection

The above solution is destructive, meaning that contents of the original set1 my change.
If you don't want to touch your existing sets, create a new set:

var result = new HashSet<>(set1);          // In Java 10 and above
Set<Integer> result = new HashSet<>(set1); // In Java < 10
result.addAll(set2); // Union
result.retainAll(set2); // Intersection

Upvotes: 82

David Lilljegren
David Lilljegren

Reputation: 1949

While guava for sure is neater and pretty much standard, here's a non destructive way to do union and intersect using only standard Java

Set s1 = Set.of(1,2,3);
Set s2 = Set.of(3,4,5);     

Set union = Stream.concat(s1.stream(),s2.stream()).collect(Collectors.toSet()); 
Set intersect = s1.stream().filter(s2::contains).collect(Collectors.toSet());

Upvotes: 33

Nitin Bisht
Nitin Bisht

Reputation: 5361

You can achieve this using Google's Guava library. The following explanation is given below with the help of an example:

    // Set a
    Set<String> a = new HashSet<String>();
    a.add("x");
    a.add("y");
    a.add("z");

    // Set b
    Set<String> b = new HashSet<String>();
    b.add("x");
    b.add("p");
    b.add("q");

Now, Calculating Intersection of two Set in Java:

Set<String> intersection = Sets.intersection(a, b);
System.out.printf("Intersection of two Set %s and %s in Java is %s %n",
                a.toString(), b.toString(), intersection.toString());

Output: Intersection of two Set [z, y, x] and [q, p, x] in Java is [x]

Similarly, Calculating Union of two Set in Java:

Set<String> union = Sets.union(a, b);
System.out.printf("Union of two Set %s and %s in Java is %s %n",
                a.toString(), b.toString(), union.toString());

Output: Union of two Set [z, y, x] and [q, p, x] in Java is [q, p, x, z, y]

You can read more about guava library at https://google.github.io/guava/releases/18.0/api/docs/

In order to add guava library to your project, You can see https://stackoverflow.com/a/4648947/8258942

Upvotes: 14

Related Questions