Java 查找集合的所有子集 (PowerSet)

Finding all subsets of a set (PowerSet)

提问by SharonKo

I want to find all subsets of a given set. I got string set defined as following: HashSet<String> Land I want to use in a loop all of its subsets as: for each do something. Is there an easy way with low complexity to do that?

我想找到给定集合的所有子集。我的字符串集定义如下：HashSet<String> L我想在循环中使用它的所有子集作为：for each do something。有没有一种简单的低复杂度的方法来做到这一点？

回答by Philipp Seeger

So you want to find all non empty SubSets of a Set, which would be {a}{b}{ab} for the set {ab}? Maybe not the fastest solution, but you could go through all elements in your set one by one, start with the first one, and determine all non empty sets -> the first element, go to the second element and copy all sets stored so far and add to all copied ones the new element plus and a new set with only the new element. Now you have all subsets of the previous elements plus a set of all those sets with the extra element added plus one with the new element alone. This can then be repeated for all elements and should give all non empty subsets.

所以你想找到一个集合的所有非空子集，对于集合 {ab}，这将是 {a}{b}{ab}？也许不是最快的解决方案，但您可以一个一个地遍历集合中的所有元素，从第一个开始，并确定所有非空集合 -> 第一个元素，转到第二个元素并复制到目前为止存储的所有集合并向所有复制的元素添加新元素 plus 和仅包含新元素的新集合。现在，您拥有先前元素的所有子集以及所有这些集合的集合，其中添加了额外的元素，再加上一个单独的新元素。然后可以对所有元素重复此操作，并且应该给出所有非空子集。

Set<String> inputSet = new HashSet<String>();

inputSet.add("a");
inputSet.add("b");
inputSet.add("c");
inputSet.add("d");

List<Set<String>> subSets = new ArrayList<Set<String>>();
for(String addToSets:inputSet) {
    List<Set<String>> newSets = new ArrayList<Set<String>>();
    for(Set<String> curSet:subSets) {
        Set<String> copyPlusNew = new HashSet<String>();
        copyPlusNew.addAll(curSet);
        copyPlusNew.add(addToSets);
        newSets.add(copyPlusNew);
    }
    Set<String> newValSet = new HashSet<String>();
    newValSet.add(addToSets);
    newSets.add(newValSet);
    subSets.addAll(newSets);
}

for(Set<String> set:subSets) {
    for(String setEntry:set) {
        System.out.print(setEntry + " ");
    }
    System.out.println();
}

Which would output:

这将输出：

d 
d b 
b 
d c 
d b c 
b c 
c 
d a 
d b a 
b a 
d c a 
d b c a 
b c a 
c a 
a

回答by SharonKo

OK, I used this algorithm (Lis a set of strings):

好的，我使用了这个算法（L是一组字符串）：

powerSet = new HashSet<List<String>>();
List<String> mainList = new ArrayList<String>(L);
buildPowerSet(mainList,mainList.size());

And,

和，

private static void buildPowerSet(List<String> list, int count)
{
    powerSet.add(list);

    for(int i=0; i<list.size(); i++)
    {
        List<String> temp = new ArrayList<String>(list);
        temp.remove(i);
        buildPowerSet(temp, temp.size());
    }
}