Wie generiert man effizient das Powerset einer Menge in Java?

Potenzmengen in Java finden: Ein effizienter Ansatz

Die Potenzmenge einer Menge umfasst alle möglichen Teilmengen der ursprünglichen Menge. Für eine Menge der Größe n enthält die Powermenge 2^n Elemente. In Java ist es üblich, die Erstellung von Powersets mit effizienten Algorithmen abzuwickeln.

Betrachten Sie das Beispiel:

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

Mit diesem Setup besteht die Aufgabe darin, die getPowerset-Funktion zu entwerfen, die das Powerset von mySet mit optimaler Zeitkomplexität generiert.

Optimale Zeitkomplexität: O (2^n)

Wie bereits erwähnt, enthält das Powerset 2^n Elemente. Daher erfordert die Generierung all dieser Elemente von Natur aus eine O(2^n)-Zeitkomplexität.

Implementierung

Der folgende Code bietet eine generische und effiziente Implementierung:

public static Set> powerSet(Set 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 : powerSet(rest)) {
    Set<T> newSet = new HashSet<>();
    newSet.add(head);
    newSet.addAll(set);
    sets.add(newSet);
    sets.add(set);
}
return sets;

}

Beispiel

Verwendung des zuvor bereitgestellten Beispiels:

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

System.out.println(s);

}

Die Ausgabe erfolgt sei:

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

Dies demonstriert die Erstellung der Potenzmenge der angegebenen Menge mit O(2^n)-Zeit Komplexität.

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