英文:
Find all possible combinations of compatible elements
问题
我设置了
{A,B,C,D,E}
并且我有一个表示元素是否兼容的集合映射(在代码示例中为 someMapWithSets):
A: B,C -(表示 A 与 B、C 等兼容)
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;
}
但是,这段代码无法正常工作,因为它不能定义所有可能的组合,只能定义其中的一些。我尝试过存储未处理的元素的数据,但代码变得非常复杂,难以理解。
我陷入了实现中。请帮忙。也许有一些这个任务的众所周知的算法?谢谢。
英文:
I have set
{A,B,C,D,E}
And I have a map (someMapWithSets in the code example) of sets which indicates if elements are compatible:
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
I need to have a map of sets where all possible combinations of compatible elements are present (largest set possible) with values like (don't care about key):
A,B,C
B,E
D,E
So as I part of the solution I thought I could create a method that retains only compatible elements for the given set and chosen element.
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;
}
But this code does not work properly because it is not capable to define all possible combinations, only a few of them. I've tried to store data about elements that were not processed but the code became very complex to be understandable.
I am stuck with implementation. Please help. Maybe there is some well-known algorithm for this task? Thank you.
答案1
得分: 0
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;
}
请注意,我已经按照您的要求将内容进行了翻译。如有任何问题,请随时提问。
英文:
Bron-Kerbosch is used in result.
https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
https://iq.opengenus.org/bron-kerbosch-algorithm/
Brute force code looks like this
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;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论