java 计算幂集的算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1422626/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Algorithm for calculating the power set
提问by rejeep
I just discovered an algorithm for finding the power set. I googled after solutions, but found none that worked any good, so I figured out one myself. But I wonder what algorithm it is, because I cannot find it on the net or in any books. I mean, does it have a name? Compared to the algorithms I found on some sites for calculating the power set, I think mine is far better and wonder why no one uses it?
我刚刚发现了一种寻找幂集的算法。我搜索了解决方案，但没有发现任何好的解决方案，所以我自己想出了一个。但是我想知道它是什么算法，因为我在网络或任何书籍中都找不到它。我的意思是，它有名字吗？与我在一些网站上找到的计算幂集的算法相比，我认为我的要好得多，为什么没有人使用它？
This is the algorithm:
这是算法：
R <- []
L <- [ e1, e2 ... en ]
c <- 0
function: powerSet(L, c)
R <- R union L
for e in L starting at c
powerSet(L\{e}, c)
end
return R
end
And here it is implemented in Java:
这里是用 Java 实现的：
public static void powerSet(List<String> list, int count)
{
result.add(list);
for(int i = count; i < list.size(); i++)
{
List<String> temp = new ArrayList<String>(list);
temp.remove(i);
powerSet(temp, i);
}
}
回答by Jo?o Silva
Mainly for two reasons:
主要有两个原因：
- It uses globalvariables;
- It is recursive, although this doesn't really matter much because it's an
O(2^n)algorithm.
- 它使用全局变量；
- 它是递归的，尽管这并不重要，因为它是一种
O(2^n)算法。
回答by Richie Cotton
Take a look at the Rosetta Code Power Setpage. There are a few implementations of recursive solutions there (including a Java one). In general though, a recursive solution implies a crazily large call stack which slows things down.
查看Rosetta Code Power Set页面。那里有一些递归解决方案的实现（包括 Java 一个）。但总的来说，递归解决方案意味着一个非常大的调用堆栈，这会减慢速度。
回答by Michiel Rop
public final static Set<Set<Character>> powerSet(Set<Character> s){
Set<Set<Character>> result = new HashSet<Set<Character>>();
result.add(s);
for (Character c:s){
Set<Character> subSet = new HashSet<Character>(s);
subSet.remove(c);
result.addAll(powerSet(subSet));
}
return result;
}
