{1, 2, 3}的幂集是：
{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}
假设我有一个Java中的Set：
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)）
是的，它确实是 O(2^n)，因为您需要生成 2^n 种可能的组合。这里有一个使用泛型和集合的工作实现：
public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
Set<Set<T>> sets = new HashSet<Set<T>>();
if (originalSet.isEmpty()) {
sets.add(new HashSet<T>());
return sets;
}
List<T> list = new ArrayList<T>(originalSet);
T head = list.get(0);
Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
for (Set<T> set : powerSet(rest)) {
Set<T> newSet = new HashSet<T>();
newSet.add(head);
newSet.addAll(set);
sets.add(newSet);
sets.add(set);
}
return sets;
}
根据您的示例输入，进行一次测试：
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : SetUtils.powerSet(mySet)) {
System.out.println(s);
}
O(2^n)吗？这是幂集中集合的数量，但每个集合都必须在内存中创建，这需要至少与集合大小成比例的时间。根据Wolfram Alpha，它是O(n * 2^n)：Wolfram Alpha查询。 - fabian实际上，我已经编写了 O(1) 的代码来完成你所要求的操作。问题是你接下来打算对 Set 做什么操作。如果你只是在调用 size()，那就是 O(1)，但如果你在迭代它，那显然是 O(2^n)。
contains() 是 O(n)，等等。
你真的需要这个吗？
编辑：
这个代码现在可以通过 Guava 中的方法 Sets.powerSet(set) 进行调用，具体的代码可参考 Guava 的 GitHub 仓库。
这里有一个解决方案，我使用了生成器，优点是整个幂集不会一次性存储...因此，您可以逐个迭代它，而无需将其存储在内存中。我认为这是更好的选择...请注意，复杂度相同，为O(2^n)，但内存要求降低了（假设垃圾收集器表现良好！ ;)）
/**
*
*/
package org.mechaevil.util.Algorithms;
import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
/**
* @author st0le
*
*/
public class PowerSet<E> implements Iterator<Set<E>>,Iterable<Set<E>>{
private E[] arr = null;
private BitSet bset = null;
@SuppressWarnings("unchecked")
public PowerSet(Set<E> set)
{
arr = (E[])set.toArray();
bset = new BitSet(arr.length + 1);
}
@Override
public boolean hasNext() {
return !bset.get(arr.length);
}
@Override
public Set<E> next() {
Set<E> returnSet = new TreeSet<E>();
for(int i = 0; i < arr.length; i++)
{
if(bset.get(i))
returnSet.add(arr[i]);
}
//increment bset
for(int i = 0; i < bset.size(); i++)
{
if(!bset.get(i))
{
bset.set(i);
break;
}else
bset.clear(i);
}
return returnSet;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not Supported!");
}
@Override
public Iterator<Set<E>> iterator() {
return this;
}
}
调用它时，请使用以下模式：
Set<Character> set = new TreeSet<Character> ();
for(int i = 0; i < 5; i++)
set.add((char) (i + 'A'));
PowerSet<Character> pset = new PowerSet<Character>(set);
for(Set<Character> s:pset)
{
System.out.println(s);
}
这是从我的Project Euler库中获取的... :)
假设 n < 63，这是一个合理的假设，因为你试图构建幂集（除非使用迭代器实现），否则会用尽内存。这是一种更简洁的方法。二进制操作比使用Math.pow()和数组来掩码更快，但Java用户似乎害怕使用它们...
List<T> list = new ArrayList<T>(originalSet);
int n = list.size();
Set<Set<T>> powerSet = new HashSet<Set<T>>();
for( long i = 0; i < (1 << n); i++) {
Set<T> element = new HashSet<T>();
for( int j = 0; j < n; j++ )
if( (i >> j) % 2 == 1 ) element.add(list.get(j));
powerSet.add(element);
}
return powerSet;
i < (1 << n)，这是等价的。 - Andrew Mao((i >> j) &1) == 1而不是(i >> j) % 2 == 1。另外，long是有符号的，所以你认为检查溢出是否有意义？ - Ravi Tiwari点击这里查看教程。
public class PowerSet {
/**
* @param args
*/
public static void main(String[] args) {
PowerSet ps = new PowerSet();
Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(2);
set.add(3);
for (Set<Integer> s : ps.powerSet(set)) {
System.out.println(s);
}
}
public Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
// Original set size e.g. 3
int size = originalSet.size();
// Number of subsets 2^n, e.g 2^3 = 8
int numberOfSubSets = (int) Math.pow(2, size);
Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
ArrayList<Integer> originalList = new ArrayList<Integer>(originalSet);
for (int i = 0; i < numberOfSubSets; i++) {
// Get binary representation of this index e.g. 010 = 2 for n = 3
String bin = getPaddedBinString(i, size);
//Get sub-set
Set<Integer> set = getSet(bin, originalList));
sets.add(set);
}
return sets;
}
//Gets a sub-set based on the binary representation. E.g. for 010 where n = 3 it will bring a new Set with value 2
private Set<Integer> getSet(String bin, List<Integer> origValues){
Set<Integer> result = new HashSet<Integer>();
for(int i = bin.length()-1; i >= 0; i--){
//Only get sub-sets where bool flag is on
if(bin.charAt(i) == '1'){
int val = origValues.get(i);
result.add(val);
}
}
return result;
}
//Converts an int to Bin and adds left padding to zero's based on size
private String getPaddedBinString(int i, int size) {
String bin = Integer.toBinaryString(i);
bin = String.format("%0" + size + "d", Integer.parseInt(bin));
return bin;
}
}
powerSet()方法。MutableSet<Integer> set = UnifiedSet.newSetWith(1, 2, 3);
System.out.println("powerSet = " + set.powerSet());
// prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
注意: 我是 Eclipse Collections 的提交者。
我希望你能提供一个比这里发布的解决方案更小巧的解决方法。此方案针对Java 7，因此需要为版本5和6粘贴一些代码。
Set<Set<Object>> powerSetofNodes(Set<Object> orig) {
Set<Set<Object>> powerSet = new HashSet<>(),
runSet = new HashSet<>(),
thisSet = new HashSet<>();
while (powerSet.size() < (Math.pow(2, orig.size())-1)) {
if (powerSet.isEmpty()) {
for (Object o : orig) {
Set<Object> s = new TreeSet<>();
s.add(o);
runSet.add(s);
powerSet.add(s);
}
continue;
}
for (Object o : orig) {
for (Set<Object> s : runSet) {
Set<Object> s2 = new TreeSet<>();
s2.addAll(s);
s2.add(o);
powerSet.add(s2);
thisSet.add(s2);
}
}
runSet.clear();
runSet.addAll(thisSet);
thisSet.clear();
}
powerSet.add(new TreeSet());
return powerSet;
Set<Object> hs = new HashSet<>();
hs.add(1);
hs.add(2);
hs.add(3);
hs.add(4);
for(Set<Object> s : powerSetofNodes(hs)) {
System.out.println(Arrays.toString(s.toArray()));
}
这里有一个简单的迭代 O(2^n) 解决方案：
public static Set<Set<Integer>> powerSet(List<Integer> intList){
Set<Set<Integer>> result = new HashSet();
result.add(new HashSet());
for (Integer i : intList){
Set<Set<Integer>> temp = new HashSet();
for(Set<Integer> intSet : result){
intSet = new HashSet(intSet);
intSet.add(i);
temp.add(intSet);
}
result.addAll(temp);
}
return result;
}
import java.util.Set;
import com.google.common.collect.*;
Set<Set<Integer>> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3));