Wie generiert man alle möglichen Satzpartitionen eines Arrays in Python?

Partitionen in Python festlegen

Das Aufteilen eines Arrays in verschiedene Teilmengen, wobei jedes Element zu genau einer Teilmenge gehört, wird als Mengenpartitionierung bezeichnet. Wie können wir bei einem gegebenen Array von Elementen alle möglichen Mengenpartitionen mit Python generieren?

Betrachten Sie ein Array [1, 2, 3]. Unser Ziel ist es, die folgenden Partitionen zu erhalten:

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

Rekursive Lösung

Unsere Lösung nutzt Rekursion, um diese Partitionierung zu erreichen. Für eine Partition von n-1 Elementen betrachten wir zwei Optionen zur Unterbringung des n-ten Elements:

1. Hinzufügen des n-ten Elements zu einer vorhandenen Teilmenge.
2. Erstellen einer neuen Teilmenge, die nur das enthält n-tes Element.

Durch die iterative Anwendung dieser Optionen können wir alle möglichen Partitionen konstruieren.

Implementierung

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

    first = collection[0]
    for smaller in partition(collection[1:]):
        # Insert first into existing subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[first] + subset] + smaller[n+1:]
        # Create a new subset
        yield [[first]] + smaller


something = list(range(1, 5))

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

Ausgabe

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]

Diese Lösung generiert effektiv alle möglichen Satzpartitionen des angegebenen Arrays.

Das obige ist der detaillierte Inhalt vonWie generiert man alle möglichen Satzpartitionen eines Arrays in Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!