Wie generieren Sie alle Permutationen einer Liste in Python, unabhängig von der Art der Elemente in dieser Liste?
Zum Beispiel:
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
python
algorithm
permutation
combinatorics
python-2.5
Ricardo Reyes
quelle
quelle
Antworten:
Ab Python 2.6 (und wenn Sie Python 3 verwenden) haben Sie ein Standardbibliothekstool dafür :
itertools.permutations
.Wenn Sie aus irgendeinem Grund ein älteres Python (<2.6) verwenden oder nur neugierig sind, wie es funktioniert, finden Sie hier einen guten Ansatz, der von http://code.activestate.com/recipes/252178/ übernommen wurde :
Einige alternative Ansätze sind in der Dokumentation von aufgeführt
itertools.permutations
. Hier ist eine:Und eine andere, basierend auf
itertools.product
:quelle
for i in range(len(elements))
stattfor i in range(len(elements)+1)
. Tatsächlich kann sich das herausgegriffene Elementelements[0:1]
inlen(elements)
unterschiedlichen Positionen befinden, im Ergebnis jedoch nichtlen(elements)+1
.Und ab Python 2.6 :
(Wird als Generator zurückgegeben. Verwenden Sie
list(permutations(l))
diese Option , um als Liste zurückzukehren.)quelle
r
Parameter gibt, der z. B.itertools.permutations([1,2,3], r=2)
alle möglichen Permutationen generiert und 2 Elemente auswählt:[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
Der folgende Code NUR mit Python 2.6 und höher
Importieren Sie zunächst
itertools
:Permutation (Ordnungsangelegenheiten):
Kombination (Reihenfolge spielt keine Rolle):
Kartesisches Produkt (mit mehreren Iterablen):
Kartesisches Produkt (mit einem iterierbaren und sich selbst):
quelle
genannt als:
quelle
Ausgabe:
Da ich den Inhalt der Liste austausche, ist ein veränderbarer Sequenztyp als Eingabe erforderlich. ZB
perm(list("ball"))
wird funktionieren undperm("ball")
nicht, weil Sie eine Zeichenfolge nicht ändern können.Diese Python-Implementierung ist von dem Algorithmus inspiriert, der im Buch Computer Algorithms von Horowitz, Sahni und Rajasekeran vorgestellt wird .
quelle
Diese Lösung implementiert einen Generator, um zu vermeiden, dass alle Permutationen im Speicher bleiben:
quelle
In einem funktionalen Stil
Das Ergebnis:
quelle
Der folgende Code ist eine direkte Permutation einer bestimmten Liste, die als Generator implementiert ist. Da nur Verweise auf die Liste zurückgegeben werden, sollte die Liste nicht außerhalb des Generators geändert werden. Die Lösung ist nicht rekursiv und verwendet daher wenig Speicher. Funktioniert auch gut mit mehreren Kopien von Elementen in der Eingabeliste.
quelle
Ein ganz offensichtlicher Weg könnte meiner Meinung nach auch sein:
quelle
Ausgabe:
quelle
Ich habe einen Algorithmus verwendet, der auf dem Fakultätszahlensystem basiert. Für eine Liste der Länge n können Sie jede Permutation Element für Element zusammenstellen und aus den Elementen auswählen, die in jeder Phase übrig bleiben. Sie haben n Auswahlmöglichkeiten für das erste Element, n-1 für das zweite und nur eine für das letzte, sodass Sie die Ziffern einer Zahl im Fakultätsnummernsystem als Indizes verwenden können. Auf diese Weise entsprechen die Zahlen 0 bis n! -1 allen möglichen Permutationen in lexikographischer Reihenfolge.
Ausgabe:
Diese Methode ist nicht rekursiv, auf meinem Computer jedoch etwas langsamer, und xrange löst einen Fehler aus, wenn n! ist zu groß, um in eine C-lange Ganzzahl konvertiert zu werden (n = 13 für mich). Es war genug, als ich es brauchte, aber es ist bei weitem kein itertools.permutations.
quelle
Beachten Sie, dass dieser Algorithmus eine
n factorial
zeitliche Komplexität aufweist, wobein
die Länge der Eingabeliste istDrucken Sie die Ergebnisse während des Laufs aus:
Beispiel:
Ausgabe:
quelle
Man kann tatsächlich über das erste Element jeder Permutation iterieren, wie in tzwenns Antwort. Es ist jedoch effizienter, diese Lösung folgendermaßen zu schreiben:
Diese Lösung ist etwa 30% schneller, anscheinend dank der Rekursion, die auf
len(elements) <= 1
statt endet0
. Es ist auch viel speichereffizienter, da es eine Generatorfunktion (durchyield
) verwendet, wie in Riccardo Reyes 'Lösung.quelle
Dies ist inspiriert von der Haskell-Implementierung mit Listenverständnis:
quelle
Regelmäßige Implementierung (kein Ertrag - erledigt alles im Speicher):
Ertragsimplementierung:
Die Grundidee besteht darin, alle Elemente im Array für die 1. Position und dann in der 2. Position alle übrigen Elemente ohne das ausgewählte Element für die 1. Position usw. zu durchlaufen. Sie können dies mit Rekursion tun , wobei die Das Stoppkriterium führt zu einem Array mit 1 Element. In diesem Fall geben Sie dieses Array zurück.
quelle
perms = getPermutations(array[:i] + array[i+1:])
numpy
Array _>getPermutations(np.array([1, 2, 3]))
, ich sehe, dass es für eine Liste funktioniert, wurde gerade verwirrt, da das func arg istarray
:)numba
und wurde gierig nach Geschwindigkeit, also habenumpy
Für die Aufführung eine von Knuth inspirierte Numpy-Lösung (S. 22):
Das Kopieren großer Speicherblöcke spart Zeit - es ist 20x schneller als
list(itertools.permutations(range(n))
:quelle
quelle
Hier ist ein Algorithmus, der mit einer Liste arbeitet, ohne neue Zwischenlisten zu erstellen, die der Lösung von Ber unter https://stackoverflow.com/a/108651/184528 ähneln .
Sie können den Code hier selbst ausprobieren: http://repl.it/J9v
quelle
Die Schönheit der Rekursion:
quelle
Dieser Algorithmus ist der effektivste, er vermeidet das Übergeben und Manipulieren von Arrays bei rekursiven Aufrufen und funktioniert in Python 2, 3:
Verwendungszweck:
quelle
quelle
EIN ANDERER ANSATZ (ohne Bibliotheken)
Die Eingabe kann eine Zeichenfolge oder eine Liste sein
quelle
[1, 2, 3]
Rückkehr[6, 6, 6, 6, 6, 6]
print(permutation(['1','2','3']))
Haftungsausschluss: formloser Plug vom Paketautor. :) :)
Das Traber- Paket unterscheidet sich von den meisten Implementierungen darin, dass es Pseudolisten generiert, die keine Permutationen enthalten, sondern Zuordnungen zwischen Permutationen und jeweiligen Positionen in einer Reihenfolge beschreiben, sodass wie gezeigt mit sehr großen Permutationslisten gearbeitet werden kann in dieser Demo, die ziemlich sofortige Operationen und Suchvorgänge in einer Pseudoliste ausführt, die alle Permutationen der Buchstaben im Alphabet enthält, ohne mehr Speicher oder Verarbeitung als eine typische Webseite zu benötigen.
In jedem Fall können wir Folgendes tun, um eine Liste von Permutationen zu erstellen.
Ausgabe:
quelle
Generieren Sie alle möglichen Permutationen
Ich benutze Python3.4:
Testfälle:
quelle
Um Ihnen möglicherweise stundenlanges Suchen und Experimentieren zu ersparen, finden Sie hier die nicht rekursive Permutationslösung in Python, die auch mit Numba funktioniert (ab Version 0.41):
Um einen Eindruck von der Leistung zu vermitteln:
Verwenden Sie diese Version daher nur, wenn Sie sie über die Funktion njitted aufrufen müssen. Andernfalls bevorzugen Sie die Implementierung von itertools.
quelle
Ich sehe eine Menge Iteration in diesen rekursiven Funktionen, nicht gerade reine Rekursion ...
Für diejenigen unter Ihnen, die sich nicht einmal an eine einzige Schleife halten können, ist hier eine grobe, völlig unnötige, vollständig rekursive Lösung
quelle
Eine andere Lösung:
quelle
Meine Python-Lösung:
quelle
Ausgabe: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
quelle
Verwenden von
Counter
quelle