Wie generiert man effizient die Potenzmenge eines Java-Sets?

Erhalten der Potenzmenge einer Menge in Java mit optimaler Komplexität

Die Potenzmenge einer Menge ist die Sammlung aller Teilmengen dieser Menge. Für eine Menge mit n Elementen enthält die Powermenge 2^n Teilmengen.

Betrachten wir eine Java-Menge:

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

Wir möchten eine Funktion, getPowerset, schreiben, um die Powermenge von zu generieren dieses Set. Die ideale Komplexität für diese Operation ist O(2^n).

Eine mögliche Implementierung unter Verwendung der Generika und Mengen von Java ist:

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

Diese rekursive Lösung iteriert durch die Elemente der Menge, Hinzufügen zu jeder Teilmenge und Generieren einer neuen Teilmenge. Der Powerset der verbleibenden Elemente bleibt konstant erhalten.

Ein einfacher Test mit der Beispieleingabe liefert das erwartete Ergebnis:

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

Ausgabe:

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

Das obige ist der detaillierte Inhalt vonWie generiert man effizient die Potenzmenge eines Java-Sets?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!