Wie kann man in Python eine Menge in alle möglichen Teilmengen unterteilen?

Partitionieren von Sätzen in Python

Die vorliegende Aufgabe besteht darin, einen bestimmten Satz von Elementen in alle möglichen Teilmengen zu unterteilen. Beispielsweise ergibt die Partitionierung der Menge [1, 2, 3] die folgenden Teilmengen:

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

Rekursive Lösung

Ein Ansatz für dieses Problem ist die Rekursion. Bei einer gegebenen Partition von n-1 Elementen können wir sie erweitern, um eine Partition von n Elementen zu erstellen, indem wir entweder das n-te Element in eine der vorhandenen Teilmengen aufnehmen oder eine neue Singleton-Teilmenge erstellen, die nur das n-te Element enthält.

Dieser rekursive Algorithmus partitioniert den Eingabesatz effektiv und vermeidet gleichzeitig doppelte Ausgaben und unnötige Abhängigkeiten von externen Bibliotheken:

<code class="python">def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller

something = list(range(1,5))

for n, p in enumerate(partition(something), 1):
    print(n, sorted(p))</code>

Das obige ist der detaillierte Inhalt vonWie kann man in Python eine Menge in alle möglichen Teilmengen unterteilen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!