如何高效生成Java集的幂集？

在 Java 中以最佳复杂度获取集合的幂集

集合的幂集是该集合的所有子集的集合。对于包含 n 个元素的集合，幂集包含 2^n 个子集。

让我们考虑一个 Java 集合：

Set<Integer> mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);

我们想要编写一个函数 getPowerset 来生成这一套。此操作的理想复杂度是 O(2^n)。

使用 Java 泛型和集合的一种可能实现是：

public static <T> Set<Set<T>> getPowerset(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<>());
        return sets;
    }
    List<T> list = new ArrayList<>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<>(list.subList(1, list.size()));

    for (Set<T> set : getPowerset(rest)) {
        Set<T> newSet = new HashSet<>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }

    return sets;
}

此递归解决方案迭代集合的元素，将它们添加到每个子集并生成一个新的子集。它始终保持剩余元素的幂集。

使用示例输入进行简单测试会产生预期结果：

for (Set<Integer> s : getPowerset(mySet)) {
    System.out.println(s);
}

输出：

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

以上是如何高效生成Java集的幂集？的详细内容。更多信息请关注PHP中文网其他相关文章！