Wie generiert man effizient die Potenzmenge einer Menge in Java?

Generieren der Potenzmenge einer Menge in Java

Die Potenzmenge einer Menge ist die Menge aller Teilmengen dieser Menge. Die Potenzmenge von {1, 2, 3} lautet beispielsweise:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3} , {1, 2, 3}, {1}}

Angenommen, wir haben ein Set in Java:

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

Wie können wir das schreiben? getPowerset-Funktion mit der optimalen Zeitkomplexität?

Lösung

Die Zeitkomplexität der Powerset-Funktion ist O(2^n), wobei n die Anzahl der Elemente in ist das Set. Dies liegt daran, dass die Potenzmenge einer Menge mit n Elementen 2^n Teilmengen enthält.

Hier ist eine funktionierende Implementierung der getPowerset-Funktion unter Verwendung von Generika und Mengen:

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

Test

Testen wir die getPowerset-Funktion anhand des angegebenen Beispiels Eingabe:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : powerSet(mySet)) {
     System.out.println(s);
}

Dadurch wird die folgende Ausgabe gedruckt:

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

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