So erzeugen Sie alle Permutationen einer Liste in Python

Mit der Python-Standardbibliothek können Sie Permutationen einer Liste erzeugen. Wenn Sie den Ablauf anpassen möchten, kommt auch ein rekursiver oder iterativer Algorithmus infrage. Eine Permutation ist eine Anordnung ausgewählter Elemente. Anders als bei einer Kombination zählt dabei die Reihenfolge. Die Anzahl der Ergebnisse wächst faktoriell; deshalb ist es nur bei überschaubaren Eingaben praktikabel, alle Anordnungen zu erzeugen.

Permutationen mit der itertools-Bibliothek erzeugen

Für die meisten Aufgaben eignet sich itertools.permutations. Die Funktion liefert einen Iterator aus Tupeln. So können Sie die Ergebnisse einzeln verarbeiten, ohne sofort eine Liste anzulegen. Standardmäßig entspricht r der Länge der Eingabe, sodass jedes Ergebnis alle Elemente enthält. Im Beispiel erzeugt r=2 geordnete Paare; die Schleife durchläuft alle Längen von eins bis drei.

Für die Liste [1, 2, 3] gibt das Programm Folgendes aus:

from itertools import permutations

data = [1, 2, 3]
print("full:", list(permutations(data)))
print("length 2:", list(permutations(data, r=2)))
print("lengths 1 to 3:")
for r in range(1, len(data) + 1):
    print(r, list(permutations(data, r)))

full: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
length 2: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
lengths 1 to 3:
1 [(1,), (2,), (3,)]
2 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
3 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Mit dem Argument r legen Sie fest, wie viele Elemente jedes Tupel enthält. Um alle nichtleeren Längen zu erzeugen, rufen Sie die Funktion wie oben für jedes r von 1 bis zur Eingabelänge auf. itertools.permutations unterscheidet Elemente anhand ihrer Position. Kommt ein Wert in der Eingabe mehrfach vor, können daher identische Ergebnistupel entstehen.

Die vollständige Signatur und das Verhalten der Funktion finden Sie in der offiziellen Dokumentation zu itertools.

Permutationen mit einer rekursiven Funktion erzeugen

Eine rekursive Lösung wählt nacheinander jedes Element aus und stellt es jeder Permutation der übrigen Elemente voran. Der Basisfall gibt eine Liste mit einer leeren Anordnung zurück. Damit funktioniert die Konstruktion für Eingaben jeder Länge, auch für eine leere Liste. Diese Variante liefert Listen statt Tupeln und eignet sich, wenn Sie die Konstruktion nachvollziehen oder anpassen möchten.

def permute(data):
    if not data:
        return [[]]

    result = []
    for index, item in enumerate(data):
        remaining = data[:index] + data[index + 1:]
        for tail in permute(remaining):
            result.append([item] + tail)
    return result

print(permute([1, 2, 3]))

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

Bei jedem rekursiven Aufruf wird eine Position entfernt. Dadurch wird die verbleibende Eingabe kleiner, bis der Basisfall erreicht ist. Gleiche Werte an verschiedenen Positionen können weiterhin identische Listen ergeben. Diese Implementierung speichert sämtliche Ergebnisse und führt viele rekursive Aufrufe aus. Sie eignet sich daher vor allem zum Lernen oder für kleine Eingaben. Wenn Sie keine eigene Konstruktion benötigen, verwenden Sie den Iterator der Standardbibliothek.

Permutationen iterativ erzeugen

Eine weitere Möglichkeit ist, jedes neue Element an jeder möglichen Position in die bereits gesammelten Teilanordnungen einzufügen. Die Ergebnisliste beginnt mit einer leeren Anordnung. Bei jedem Schritt wächst ihre Größe um den Faktor der Anzahl der bis dahin verarbeiteten Elemente. Dieses Verfahren kommt ohne rekursive Aufrufe aus, speichert aber weiterhin alle Ergebnisse.

def iterative_permute(data):
    results = [[]]
    for item in data:
        next_results = []
        for ordering in results:
            for index in range(len(ordering) + 1):
                next_results.append(ordering[:index] + [item] + ordering[index:])
        results = next_results
    return results

print(iterative_permute([1, 2, 3]))

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

Die Einfügereihenfolge bestimmt, in welcher Reihenfolge dieses Verfahren die Ergebnisse zurückgibt. Welche Permutationen entstehen, ändert sich dadurch nicht. Wählen Sie diese Methode, wenn die schrittweise Konstruktion zu Ihrer Aufgabe passt, und berücksichtigen Sie den Speicherbedarf, wenn Sie alle Ergebnisse aufbewahren.

Fazit

Verwenden Sie itertools.permutations, wenn Sie einen knappen Iterator benötigen, der Ergebnisse schrittweise liefert. Mit r legen Sie eine bestimmte Länge fest. Rekursion oder iterative Einfügung eignen sich, wenn Sie die Konstruktion anpassen oder nachvollziehen möchten. Eine Liste mit n Positionen hat n! vollständige Permutationen. Daher wachsen sowohl die Verarbeitungszeit als auch der Speicherbedarf einer vollständig aufgebauten Ergebnisliste schnell. Bei größeren Eingaben können Sie die Ergebnisse nach Bedarf aus dem Iterator verarbeiten oder nur die für Ihre Aufgabe relevanten Längen und Auswahlen erzeugen.

Häufig gestellte Fragen

1. Was ist eine Permutation?
   Eine Permutation ist eine geordnete Auswahl von Elementen. [1, 2] und [2, 1] sind beispielsweise unterschiedliche Permutationen, weil ihre Reihenfolge abweicht.

2. Wie funktioniert itertools.permutations?
   Die Funktion liefert Tupel der Länge r aus dem Eingabe-Iterable. Wenn Sie r weglassen, wird die gesamte Eingabelänge verwendet. Die Ergebnisse entstehen schrittweise. Wandeln Sie den Iterator in eine Liste um, wird jedoch jedes Ergebnis im Speicher abgelegt.

3. Was geschieht, wenn die Eingabe doppelte Werte enthält?
   Die Funktion berücksichtigt Positionen und nicht, ob Werte gleich sind. Doppelte Eingabewerte können deshalb identische Tupel hervorbringen. Wenn die Elemente hashbar sind, lassen sich wiederholte Tupel nach der Erzeugung durch Umwandeln in eine Menge entfernen. Die doppelten Ergebnisse werden dadurch aber nicht von vornherein vermieden. Um doppelte Arbeit zu sparen, benötigen Sie einen Algorithmus, der bei jedem Schritt gleiche Auswahlmöglichkeiten überspringt.

4. Wie viele Permutationen gibt es?
   Bei n verschiedenen Positionen gibt es n! Permutationen, die alle Elemente enthalten. Werden nur r Positionen ausgewählt, beträgt die Anzahl n! / (n - r)!.

5. Wie groß darf die Eingabe sein?
   Eine feste Größenbegrenzung, die für jede Maschine und Aufgabe gilt, gibt es nicht. Wegen des faktoriellen Wachstums kann schon eine mittelgroße Eingabe aufwendig zu verarbeiten sein. Wenn Sie alle Ergebnisse speichern, benötigen Sie außerdem viel Arbeitsspeicher. Verwenden Sie nach Möglichkeit den Iterator oder ein kleineres r, wenn Sie nicht alle vollständigen Ergebnisse auf einmal brauchen.