Reputation: 24790
What is the simplest way to make a union or an intersection of Set
s in Java? I've seen some strange solutions to this simple problem (e.g. manually iterating the two sets).
Upvotes: 58
Views: 101962
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
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
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
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
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
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
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