java - How do I take the union of sets?

Question

Is there any optimal way to get all union of n sets?

This is what I have done, but it is very slow for a large number of sets:

public static void main(String[] args) {
    List<List<Set<Integer>>> unionSet = new ArrayList<>();
    List<List<Integer>> sets = ...
    double avail = 0;
    for (int i = 1; i <= sets.size(); i++) {
        List<Set<Integer>> us = new ArrayList<>();
        union(sets, us, new HashSet<>(), i, 0);
        unionSet.add(us);
    }
}

public static void union(
        List<List<Integer>> sets, List<Set<Integer>> unionSet,
        Set<Integer> set, int size, int index) {
    for (int i = index; i < sets.size(); i++) {
        Set temp = new HashSet(set);
        temp.addAll(sets.get(i));

        if (size != 1)
            union(sets, unionSet, temp, size - 1, i + 1);
        else
            unionSet.add(temp);
    }
}

The intersection of all combinations of n sets

Answer 1

You can use Stream#flatMap method as follows:

1. If you have a list of sets, you can flatten its elements (i.e. sets) into one set of unique values:

   List<Set<Integer>> setList =
           List.of(Set.of(1, 2, 3), Set.of(2, 3, 7));
   
   Set<Integer> set = setList.stream()
           .flatMap(Set::stream)
           .collect(Collectors.toSet());
   
   System.out.println(set); // [1, 2, 3, 7]
   

2. If you have a deeper level of nesting, then you have to perform a deeper flattening:

   List<List<Set<Integer>>> lists = List.of(
           List.of(Set.of(1, 2, 3), Set.of(2, 3, 4)),
           List.of(Set.of(3, 4, 5), Set.of(5, 1, 2)));
   
   Set<Integer> set = lists
           // Stream<List<Set<Integer>>>
           .stream()
           // Stream<Set<Integer>>
           .flatMap(List::stream)
           // Stream<Integer>
           .flatMap(Set::stream)
           .collect(Collectors.toSet());
   
   System.out.println(set); // [1, 2, 3, 4, 5]
   

3. If you have several collections with unknown level of nesting, you can create a generic recursive flattening method:

   public static void main(String[] args) {
       List<Set<Integer>> setList =
               List.of(Set.of(1, 2, 3), Set.of(2, 3, 7));
   
       List<List<Set<Integer>>> lists = List.of(
               List.of(Set.of(1, 2, 3), Set.of(2, 3, 4)),
               List.of(Set.of(3, 4, 5), Set.of(5, 1, 2)));
   
       Set<Integer> set = (Set<Integer>) toSet(setList, lists);
       System.out.println(set); // [1, 2, 3, 4, 5, 7]
   }
   

   public static Set<?> toSet(Collection<?>... collections) {
       return Arrays.stream(collections)
               .flatMap(col -> flattenStream(col.stream()))
               .collect(Collectors.toSet());
   }
   

   public static Stream<?> flattenStream(Stream<?> stream) {
       return stream.flatMap(e -> {
           if (e instanceof Collection) {
               return flattenStream(((Collection<?>) e).stream());
           } else {
               return Stream.of(e);
           }
       });
   }
   

---

^{See also:
? Parallelized Matrix Multiplication
? The intersection of all combinations of n sets}