Java 8 - объединить все подмножества, содержащие общие элементы

Question

Начиная с набора наборов «групп»:

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

Я хочу создать новый список наборов, объединив все подмножества с общими элементами:

т.е. начиная с наборовниже:

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}

Окончательный результат будет:

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

Любые советы о том, как этого добиться, будут оценены.

РЕДАКТИРОВАТЬ: В случае неровных сетовон будет выполнять то же самое.Таким образом, если бы это был метод, он псевдо выглядел бы так:

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

}

Вывод на консоль:

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

Answer 1

Вы можете просто реализовать алгоритм так, как вы его описали в постановке задачи, - найти пересекающиеся множества и объединять их, пока нечего объединять.Стандартная библиотека имеет метод Collections.disjoint, который помогает определить, имеют ли две коллекции общие элементы:

// 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);
}

Answer 2

Вот обязательный путь, основанный на решении @NiksVij.Очевидно, что решение @NiksVij не является правильным, и этот ответ направлен на то, чтобы это исправить и расширить немного:

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

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();
            }
        }
    }
}

Надеюсь, это поможет вместо Set<Set<String>> groups Я использовал List<Set<String>> groups для простоты использования списков. Если у вас есть ограничение на использование только Set, вы можете сгенерировать List из Set (скажем, yourSet), передав его вконструктор реализации списков, например.

groups = new ArrayList<>(yourSet);