How to Efficiently Generate the Power Set of a Java Set?

Obtaining the Powerset of a Set in Java with Optimal Complexity

The powerset of a set is the collection of all subsets of that set. For a set with n elements, the powerset contains 2^n subsets.

Let's consider a Java set:

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

We want to write a function, getPowerset, to generate the powerset of this set. The ideal complexity for this operation is O(2^n).

One possible implementation using Java's generics and sets is:

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

This recursive solution iterates through the elements of the set, adding them to each subset and generating a new subset. It consistently maintains the powerset of the remaining elements.

A simple test using the example input yields the expected result:

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

Output:

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

The above is the detailed content of How to Efficiently Generate the Power Set of a Java Set?. For more information, please follow other related articles on the PHP Chinese website!