寻找所有兼容元素的可能组合

huangapple
go评论95阅读模式
英文:

Find all possible combinations of compatible elements

问题

我设置了

  1. {A,B,C,D,E}

并且我有一个表示元素是否兼容的集合映射（在代码示例中为 someMapWithSets）：

  1. A: B,C -（表示 A 与 B、C 等兼容）
  2. B: A,E,C
  3. C: A,B
  4. D: E
  5. E: B,D

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

  1. A,B,C
  2. B,E
  3. D,E

因此，作为解决方案的一部分，我考虑创建一个方法，仅保留给定集合和选定元素的兼容元素。

  1. public static Map<String, Set<String>> defineCompatibility(Set<String> set) {
  2.     if (set.isEmpty()) {
  3.         return new HashMap<>();
  4.     }
  5.     Map<String, Set<String>> finalResult = new HashMap<>();
  6.     Set<String> elementsToDefine = new HashSet<>(set);
  7.     while (!elementsToDefine.isEmpty()) {
  8.         String currentElement = elementsToDefine.stream().findFirst().get();
  9.         Set<String> definedSet = defineForElement(set, currentElement);
  10.         finalResult.put(currentElement, definedSet);
  11.         elementsToDefine.remove(currentElement);
  12.     }
  13.     return finalResult;
  14. }
  16. private static Set<String> defineForElement(Set<String> set, String rootElement) {
  17.     Set<String> result = someMapWithSets.get(rootElement);
  18.     result.retainAll(set);
  19.     result.add(rootElement);
  20.     Set<String> tmpHolder = new HashSet<>(result);
  21.     for (String next : tmpHolder) {
  22.         if (!result.contains(next)) {
  23.             break;
  24.         }
  25.         Set<String> strings = someMapWithSets.get(next);
  26.         strings.add(next);
  27.         result.retainAll(strings);
  28.     }
  29.     return result;
  30. }

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

我陷入了实现中。请帮忙。也许有一些这个任务的众所周知的算法？谢谢。

英文:

I have set

  1. {A,B,C,D,E}

And I have a map (someMapWithSets in the code example) of sets which indicates if elements are compatible:

  1. A: B,C - (means A is compatible with B and C and etc) 
  2. B: A,E,C
  3. C: A,B
  4. D: E
  5. 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):

  1. A,B,C
  2. B,E
  3. 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.

  1. public static Map&lt;String, Set&lt;String&gt;&gt; defineCompatibility(Set&lt;String&gt; set) {
  2.     if (set.isEmpty()) {
  3.         return new HashMap&lt;&gt;();
  4.     }
  5.     Map&lt;String, Set&lt;String&gt;&gt; finalResult = new HashMap&lt;&gt;();
  6.     Set&lt;String&gt; elementsToDefine = new HashSet&lt;&gt;(set);
  7.     while (!elementsToDefine.isEmpty()) {
  8.         String currentElement = elementsToDefine.stream().findFirst().get();
  9.         Set&lt;String&gt; definedSet = defineForElement(set, currentElement);
  10.         finalResult.put(currentElement, definedSet);
  11.         elementsToDefine.remove(currentElement);
  12.     }
  13.     return finalResult;
  14. }
  16. private static Set&lt;String&gt; defineForElement(Set&lt;String&gt; set, String rootElement) {
  17.     Set&lt;String&gt; result = someMapWithSets.get(rootElement);
  18.     result.retainAll(set);
  19.     result.add(rootElement);
  20.     Set&lt;String&gt; tmpHolder = new HashSet&lt;&gt;(result);
  21.     for (String next : tmpHolder) {
  22.         if (!result.contains(next)) {
  23.             break;
  24.         }
  25.         Set&lt;String&gt; strings = someMapWithSets.get(next);
  26.         strings.add(next);
  27.         result.retainAll(strings);
  28.     }
  29.     return result;
  30. }

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/

暴力解法的代码如下：

  1. private static void define(Set<String> r, Set<String> p, Set<String> x) {
  2.     if (p.isEmpty() && x.isEmpty()) {
  3.         System.out.println("Here is maximal clique: " + r);
  4.         return;
  5.     }
  6.     Set<String> p1 = new HashSet<>(p);
  7.     for (String v : p) {
  8.         r.add(v);
  9.         define(r, intersect(p1, someMapWithSets.get(v)), intersect(x, someMapWithSets.get(v)));
  10.         r.remove(v);
  11.         p1.remove(v);
  12.         x.add(v);
  13.     }
  14. }
  16. private static Set<String> intersect(Set<String> first, Set<String> second) {
  17.     Set<String> holder = new HashSet<>(first);
  18.     holder.retainAll(second);
  19.     return holder;
  20. }

请注意，我已经按照您的要求将内容进行了翻译。如有任何问题，请随时提问。

英文:

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

  1. private static void define(Set&lt;String&gt; r, Set&lt;String&gt; p, Set&lt;String&gt; x) {
  3.     if (p.isEmpty() &amp;&amp; x.isEmpty()) {
  4.         System.out.println(&quot;Here is maximal clique: &quot; + r);
  5.         return;
  6.     }
  8.     Set&lt;String&gt; p1 = new HashSet&lt;&gt;(p);
  10.     for (String v : p) {
  11.         r.add(v);
  12.         define(r, intersect(p1, someMapWithSets.get(v)), intersect(x, someMapWithSets.get(v)));
  13.         r.remove(v);
  14.         p1.remove(v);
  15.         x.add(v);
  16.     }
  17. }
  19.     private static Set&lt;String&gt; intersect(Set&lt;String&gt; first, Set&lt;String&gt; second) {
  20.     Set&lt;String&gt; holder = new HashSet&lt;&gt;(first);
  21.     holder.retainAll(second);
  22.     return holder;
  23. }

huangapple
  • 本文由 发表于 2020年10月2日 00:27:08
  • 转载请务必保留本文链接：https://go.coder-hub.com/64159545.html
  • algorithm
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定