java - 查找兼容元素的所有可能组合

Question

我已经设定

{A,B,C,D,E}

我有一个集合的映射（代码示例中的 someMapWithSets），它指示元素是否兼容：

A: B,C - (means A is compatible with B and C and etc) 
B: A,E,C
C: A,B
D: E
E: B,D

我需要一个集合的映射，其中存在兼容元素的所有可能组合（可能的最大集合），其值如下（不关心键）：

A,B,C
B,E
D,E

因此，作为解决方案的一部分，我认为我可以创建一种方法，只保留给定集合和所选元素的兼容元素。

public static Map<String, Set<String>> defineCompatibility(Set<String> set) {
    if (set.isEmpty()) {
        return new HashMap<>();
    }
    Map<String, Set<String>> finalResult = new HashMap<>();
    Set<String> elementsToDefine = new HashSet<>(set);
    while (!elementsToDefine.isEmpty()) {
        String currentElement = elementsToDefine.stream().findFirst().get();
        Set<String> definedSet = defineForElement(set, currentElement);
        finalResult.put(currentElement, definedSet);
        elementsToDefine.remove(currentElement);
    }
    return finalResult;
}

private static Set<String> defineForElement(Set<String> set, String rootElement) {
    Set<String> result = someMapWithSets.get(rootElement);
    result.retainAll(set);
    result.add(rootElement);
    Set<String> tmpHolder = new HashSet<>(result);
    for (String next : tmpHolder) {
        if (!result.contains(next)) {
            break;
        }
        Set<String> strings = someMapWithSets.get(next);
        strings.add(next);
        result.retainAll(strings);
    }
    return result;
}

但是这段代码不能正常工作，因为它不能定义所有可能的组合，只能定义其中的几个。我尝试存储有关未处理的元素的数据，但代码变得非常复杂，难以理解。

我坚持执行。请帮忙。也许这个任务有一些众所周知的算法？谢谢你。

标签： javaalgorithm

Answer 1

结果中使用了 Bron-Kerbosch。

https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

https://iq.opengenus.org/bron-kerbosch-algorithm/

蛮力代码看起来像这样

private static void define(Set<String> r, Set<String> p, Set<String> x) {

    if (p.isEmpty() && x.isEmpty()) {
        System.out.println("Here is maximal clique: " + r);
        return;
    }

    Set<String> p1 = new HashSet<>(p);

    for (String v : p) {
        r.add(v);
        define(r, intersect(p1, someMapWithSets.get(v)), intersect(x, someMapWithSets.get(v)));
        r.remove(v);
        p1.remove(v);
        x.add(v);
    }
}

    private static Set<String> intersect(Set<String> first, Set<String> second) {
    Set<String> holder = new HashSet<>(first);
    holder.retainAll(second);
    return holder;
}