java - 查找集合的所有子集 (PowerSet)

Question

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

Answer 1

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

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

和，

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());
    }
}

Answer 2

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

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();
}

这将输出：

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