在Java中获取集合的幂集

Question

{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)。）

原文由 Manuel Araoz 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

是的，它是 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);
 }

原文由 João Silva 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

实际上，我已经编写了可以在 O(1) 中完成您所要求的代码。问题是您下一步打算 如何 处理 Set。如果你只是要调用 size() ，那就是 O(1)，但如果你要迭代它，那显然是 O(2^n) 。

contains() 将是 O(n) 等

你真的需要这个吗？

编辑：

此代码 现在在 Guava 中可用，通过方法 Sets.powerSet(set) 。

原文由 Kevin Bourrillion 发布，翻译遵循 CC BY-SA 3.0 许可协议