Wie kann ich alle Teilmengen (Powerset) einer gegebenen Menge in Python effizient generieren?

Alle Teilmengen einer Menge finden: Die Potenzmenge

Bei einer gegebenen Menge von Elementen kann das Finden aller Teilmengen eine häufige Programmieraufgabe sein . Dies wird als Konstruieren der Potenzmenge der Menge bezeichnet.

Lösung mit itertools

Das Python-Modul itertools bietet eine elegante Lösung zur Berechnung der Potenzmenge mithilfe von Kombinationen:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Wie es funktioniert

Diese Funktion generiert alle Kombinationen von Elementen in der Menge, von einer leeren Menge bis zur vollständigen Menge. Dies wird erreicht, indem der Bereich möglicher Teilmengengrößen (0 bis zur Anzahl der Elemente in der Menge) durchlaufen und für jede Größe Kombinationen von Elementen erstellt werden.

Beispiel

Zum Beispiel die Potenzmenge der Menge {0, 1, 2, 3} lautet:

list(powerset("abcd"))
[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]

Anpassung

Wenn Sie die leere Teilmenge aus dem Powerset ausschließen möchten, können Sie die Range-Anweisung in der Powerset-Funktion in range(1) ändern , len(s) 1):

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))

Das obige ist der detaillierte Inhalt vonWie kann ich alle Teilmengen (Powerset) einer gegebenen Menge in Python effizient generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!