Java 8 - Merge All Subsets Containing Common Elements

Question

Starting with a set of sets "groups":

Set<Set<String>> groups = new HashSet<>();

I want to create a new list of sets by merging all subsets with common elements:

i.e. Starting with the sets below:

A = {a, b, c}
B = {c, d, e, f}
C = {f, g, h, i, j}
D = {k, l, m}
E = {m, n, o}
F = {p, q, r}

The final result would be:

Set 1 = {a, b, c, d, e, f, g, h, i, j}
Set 2 = {k, l, m, n, o}
Set 3 = {p, q, r}

Any advice on how to accomplish this would be appreciated.

EDIT: In case of uneven sets it would perform the same. So if it were a method, it pseudo would look like this:

public void doStuff(){

  Set<Set<String>> groups = {{a,b,c}, {c,d,e,f}, {m, n, o}}

  Set<Set<String>> newGroups = mergeSubsets(groups);

  System.out.println(newGroups);
}

public Set<Set<String>> mergeSubsets(Set<Set<String>> groups){

     //some operations

}

Console out:

   New Groups: {{a,b,c,d,e,f}, {m, n, o}}

Answer 1

import java.util.*;

public class MergeSet {
    public static void main(String... args) {
        List<Set<String>> groups = new ArrayList<>();
        String[] A = {"a", "b", "c"};
        String[] B = {"c", "d", "e", "f"};
        String[] C = {"f", "g", "h", "i", "j"};
        String[] D = {"k", "l", "m"};
        String[] E = {"m", "n", "o"};
        String[] F = {"p", "q", "r"};

        groups.add(new HashSet<>(Arrays.asList(A)));
        groups.add(new HashSet<>(Arrays.asList(B)));
        groups.add(new HashSet<>(Arrays.asList(C)));
        groups.add(new HashSet<>(Arrays.asList(D)));
        groups.add(new HashSet<>(Arrays.asList(E)));
        groups.add(new HashSet<>(Arrays.asList(F)));

        Set<Set<String>> newGroups = mergeSubsets(groups);
        System.out.println(newGroups);

    }

    private static Set<Set<String>> mergeSubsets(List<Set<String>> groups) {
        List<Set<String>> newGroups = new ArrayList<>();
        Set<String> init = groups.get(0);
        groups.remove(0);
        newGroups.add(init);
        while (!groups.isEmpty()) {
            removeMergedElementFromGroupAndUpdateNewGroup(newGroups.get(newGroups.size() - 1), groups);
            if(!groups.isEmpty()) {
                init = groups.get(0);
                groups.remove(0);
                newGroups.add(init);
            }
        }
        return new HashSet<>(newGroups);
    }

    private static void removeMergedElementFromGroupAndUpdateNewGroup(Set<String> master2, List<Set<String>> masterList) {
        Iterator<Set<String>> iterator = masterList.iterator();
        while (iterator.hasNext()) {
            Set<String> strings = iterator.next();
            boolean merge = strings.stream().anyMatch(string -> master2.contains(string));
            if (merge) {
                master2.addAll(strings);
                iterator.remove();
            }
        }
    }
}

Hope this helps instead of Set<Set<String>> groups I have used List<Set<String>> groups for the ease of using lists if you have a constraint of using Set only , you can generate List from Set(say yourSet) by passing it into the constructor of Lists implementation , for eg.

groups = new ArrayList<>(yourSet);

Answer 2

Here is the imperative way based on @NiksVij solution. Obviously the solution of @NiksVij is not correct and this answer aims to fix this and extend a bit more:

public class MergeSet {

    public static void main(String... args) {
        List<Set<String>> list = new ArrayList<>();
        String[] A = {"a", "c", "e", "g"};
        String[] B = {"b", "d", "f", "h"};
        String[] C = {"c", "e", "f"};
        String[] D = {"b"};

        list.add(new HashSet<>(Arrays.asList(A)));
        list.add(new HashSet<>(Arrays.asList(C)));
        list.add(new HashSet<>(Arrays.asList(B)));
        list.add(new HashSet<>(Arrays.asList(D)));

        List<Set<String>> newGroups = merge(list);
        System.out.println(newGroups);

    }

    @SuppressWarnings("empty-statement")
    private static <T> List<Set<T>> merge(List<Set<T>> list) {
        if (list == null || list.isEmpty()) {
            return list;
        }
        List<Set<T>> merged = new ArrayList<>();
        do {
            merged.add(list.get(0));
            list.remove(0);

            while (mergeStep(merged.get(merged.size() - 1), list));
        } while (!list.isEmpty());
        return merged;
    }

    private static <T> boolean mergeStep(Set<T> setToCheck, List<Set<T>> remainingList) {
        boolean atLeastOnceMerged = false;
        Iterator<Set<T>> iterator = remainingList.iterator();
        while (iterator.hasNext()) {
            Set<T> elements = iterator.next();
            boolean doMerge = !Collections.disjoint(elements, setToCheck);
            if (doMerge) {
                atLeastOnceMerged |= doMerge;
                setToCheck.addAll(elements);
                iterator.remove();
            }
        }
        return atLeastOnceMerged;
    }

Answer 3

You can just implement the algorithm as you describe it in your problem statement -- find intersecting sets and merge them until there is nothing to merge. Standard library has a method Collections.disjoint that helps by determining if two collections have any elements in common:

// this implementation sacrifices efficiency for clarity
public Set<Set<String>> mergeSubsets(Set<Set<String>> groups) {
    Set<Set<String>> result = new HashSet<>();
    for (Set<String> set : groups) {
        // try to find a set in result that intersects this set
        // if one is found, merge the two.  otherwise, add this set to result
        result.stream()
                .filter(x -> !Collections.disjoint(x, set))
                .findAny()
                .ifPresentOrElse(   // this method was added in java 9
                        x -> x.addAll(set),
                        () -> result.add(new HashSet<>(set))
                );
    }

    // if nothing got merged we are done; otherwise, recurse and try again
    return result.size() == groups.size() ? result : mergeSubsets(result);
}