在Java中获取一个集的Powerset

Question

在Java中获取一个集的Powerset

.的权力集{1, 2, 3}是：

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

假设我有一个Set在Java中：

Set<Integer> mySet = new HashSet<Integer>();mySet.add(1);mySet.add(2);mySet.add(3);Set<Set<Integer>> powerSet = getPowerset(mySet);

如何用尽可能好的复杂性顺序编写getPowerset函数？(我认为可能是O(2^n)。)

Answer 1

是的，是的O(2^n)实际上，既然你需要生成，2^n可能的组合。下面是一个工作实现，使用泛型和集合：public&nbsp;static&nbsp;<T>&nbsp;Set<Set<T>>&nbsp;powerSet(Set<T>&nbsp;originalSet)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;Set<Set<T>>&nbsp;sets&nbsp;=&nbsp;new&nbsp;HashSet<Set<T>>(); &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(originalSet.isEmpty())&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sets.add(new&nbsp;HashSet<T>()); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;sets; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;List<T>&nbsp;list&nbsp;=&nbsp;new&nbsp;ArrayList<T>(originalSet); &nbsp;&nbsp;&nbsp;&nbsp;T&nbsp;head&nbsp;=&nbsp;list.get(0); &nbsp;&nbsp;&nbsp;&nbsp;Set<T>&nbsp;rest&nbsp;=&nbsp;new&nbsp;HashSet<T>(list.subList(1,&nbsp;list.size()));&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(Set<T>&nbsp;set&nbsp;:&nbsp;powerSet(rest))&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Set<T>&nbsp;newSet&nbsp;=&nbsp;new&nbsp;HashSet<T>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newSet.add(head); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newSet.addAll(set); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sets.add(newSet); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sets.add(set); &nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;sets;}以及一个测试，给出您的示例输入：&nbsp;Set<Integer>&nbsp;mySet&nbsp;=&nbsp;new&nbsp;HashSet<Integer>(); &nbsp;mySet.add(1); &nbsp;mySet.add(2); &nbsp;mySet.add(3); &nbsp;for&nbsp;(Set<Integer>&nbsp;s&nbsp;:&nbsp;SetUtils.powerSet(mySet))&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(s); &nbsp;}

Answer 2

这里有一个解决方案，我使用发电机，优点是，整个功率集从来没有存储在一次.。因此，您可以一个地迭代它，而不需要将它存储在内存中。我想这是个更好的选择.。注意复杂性是相同的，O(2^n)，但是内存需求减少了(假设垃圾收集器运行！；)/** &nbsp;* &nbsp;*/package&nbsp;org.mechaevil.util.Algorithms;import&nbsp;java.util.BitSet;import&nbsp;java.util.Iterator;import&nbsp;java.util.Set;import&nbsp;java.util.TreeSet;/** &nbsp;*&nbsp;@author&nbsp;st0le &nbsp;* &nbsp;*/public&nbsp;class&nbsp;PowerSet<E>&nbsp;implements&nbsp;Iterator<Set<E>>,Iterable<Set<E>>{ &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;E[]&nbsp;arr&nbsp;=&nbsp;null; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;BitSet&nbsp;bset&nbsp;=&nbsp;null; &nbsp;&nbsp;&nbsp;&nbsp;@SuppressWarnings("unchecked") &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;PowerSet(Set<E>&nbsp;set) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr&nbsp;=&nbsp;(E[])set.toArray(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bset&nbsp;=&nbsp;new&nbsp;BitSet(arr.length&nbsp;+&nbsp;1); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;@Override &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;boolean&nbsp;hasNext()&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;!bset.get(arr.length); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;@Override &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;Set<E>&nbsp;next()&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Set<E>&nbsp;returnSet&nbsp;=&nbsp;new&nbsp;TreeSet<E>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;arr.length;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(bset.get(i)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;returnSet.add(arr[i]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//increment&nbsp;bset &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;bset.size();&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(!bset.get(i)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bset.set(i); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bset.clear(i); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;returnSet; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;@Override &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;void&nbsp;remove()&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;throw&nbsp;new&nbsp;UnsupportedOperationException("Not&nbsp;Supported!"); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;@Override &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;Iterator<Set<E>>&nbsp;iterator()&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;this; &nbsp;&nbsp;&nbsp;&nbsp;}}要调用它，请使用以下模式：&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Set<Character>&nbsp;set&nbsp;=&nbsp;new&nbsp;TreeSet<Character>&nbsp;(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;5;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;set.add((char)&nbsp;(i&nbsp;+&nbsp;'A')); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;PowerSet<Character>&nbsp;pset&nbsp;=&nbsp;new&nbsp;PowerSet<Character>(set); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(Set<Character>&nbsp;s:pset) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(s); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}这是我的欧拉项目图书馆.。*)