在 Java 中获取集合的幂集

algorithm java set powerset

2022-08-31 11:42:10

的幂集是：{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）。

答案 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);
 }

答案 2

实际上，我已经编写了代码，可以完成您在O（1）中所要求的。问题是你接下来打算用“集”做什么。如果你只是要调用它，那就是O（1），但是如果你要迭代它，那显然是.size()O(2^n)

contains()将是，等等。O(n)

你真的需要这个吗？

编辑：

此代码现在在番石榴中可用，通过 Sets.powerSet（set） 方法公开。