Java 8 - 合并包含共同元素的所有子集

Question

从一组集合“groups”开始：

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}}

- user1870035

---

任意两个由非空交集组成的子集应该合并。我相信这可以用某种递归解决方案来解决，但我现在很难弄清楚。 - user1870035

在纸上解决它 - 显然有一个算法在其背后。然后编写Java代码。 - UninformedUser

请使用以下代码或搜索此链接（https://dev59.com/DJ_ha4cB1Zd3GeqPthwb）中的Python解决方案，以合并具有共同元素的集合。 - UninformedUser

你的结果集为什么有两个 c？ - shmosel

好的，我明白了。那么{{a，b，c}，{c，d，e，f}，{e，n，o}}呢？这个会输出什么？ - Naman

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

- Misha

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

- maloku

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

希望这可以帮到你，我使用了List<Set<String>> groups而不是Set<Set<String>> groups，因为使用列表更加方便。如果你有只能使用Set的限制，你可以通过将其传递到Lists实现的构造函数中来从Set（比如yourSet）生成List，例如：

groups = new ArrayList<>(yourSet);

- NiksVij

---

这对于 String[] A = {"a", "c", "e", "g"}; String[] B = {"b", "d", "f", "h"}; String[] C = {"c", "e", "f"}; String[] D = {"b"}; 不起作用。 - maloku

逻辑没问题。只是缺少了一个空值检查。已经添加了该检查。感谢指出这个错误。 - NiksVij