Welche Möglichkeiten gibt es 5 verschiedene Elemente unterschiedlich anzuorden?
2016-06-13 KombinatorikPython
Wiebke kommt vom Fischmarkt zurück und hat fünf alte Vasen eingekauft. Stolz zeigt sie ihrem Lebensabschnittsgefährten Friedolin auf dem Regal ihre Ausbeute. “Sind sie nicht wunderschön,” meint sie. “Mja”, grunzt er. “Aber sie stehen noch nicht richtig. Schatz, tausche doch mal die beiden äußeren Vasen aus.” “OK!” “Mhhh, geht vielleicht noch besser. Am besten probieren wir einfach alle Möglichkeiten einmal aus.” Friedolin reißt die Augen auf: “Bist Du verrückt, dass sind doch mehr als … Möglichkeiten.”
Ja, wieviele Möglichkeiten gibt es eigentlich fünf unterscheidbare Elemente anzuordnen? Diese Problem fällt in den Bereich der Kombinatorik. Man redet in diesem Fall von Permutationen. Mathematisch ist diese Aufgabe einfach zu lösen. Für den ersten Platz kommen fünf Vasen in Frage. Für den zweiten Platz kommen dann nur noch vier Vasen in Frage. Es gibt fünf mal vier, also 20 Möglichkeiten zwei aus den fünf Vasen anzuorden. Für den dritten Platz stehen dann noch drei Vasen zur Auswahl, für den vierten Platz zwei Vasen und für den letzten schließlich nur eine Vase. Also gibt es 5 mal 4 mal 3 mal 2 mal 1 gleich 120 Möglichkeiten bzw. Permutationen die fünf Vasen anzuordnen.
Und welches sind die Möglichkeiten? Man könnte sich jetzt mit Bleistift und Papier hinsetzen um alle Möglichkeiten durchzuprobieren, aber so eine stupide Arbeit sollte man doch einem Rechner überlassen. Um eine beliebige Anzahl von Elementen permutieren zu können empfiehlt sich hier die Anwendung der rekursiven Programmierung. Bei dieser Methode ruft sich eine Funktion mit neuen Parametern selber auf, bis es zu einer eindeutigen Lösung kommt.
Schritt für Schritt
# Liste der zu permutierenden Elemente
liste = ["1","2","3","4","5"]
Alle zu kombinierenden Elemente befinden sich in der Liste liste. Hier sind es die Zahlen 1 bis 5.
# Funktionen
def kombiniere(l):
Die Funktion kombiniere(l) erledigt die eigentliche Arbeit. Dabei gibt es zwei Situationen für die Funktion. Die Liste enthält ein Element oder die Liste enthält mehr als ein Element.
# Wenn die Liste mehr als ein Element enthält
if len(l) > 1:
erg = []
# Alle Elemente der Liste bearbeiten
for i in range(len(l)):
Die Liste enthält mehr als ein Element, also müssen wir jedes Element bearbeiten. Das Ergebnis ist in der Liste erg gespeichert.
# Den Fortschritt nur auf der obersten Ebene anzeigen
if (len(liste) == len(l)):
print(i)
Wenn eine große Anzahl von Elementen angeordnet werden muss, kann die Berechnung auch etwas länger dauern. Dann ist es von Vorteil, wenn das Programm von Zeit zu Zeit anzeigt, wie weit es ist und es auch noch lebt. Da allerdings die Ausgabe sehr viel Zeit kostet, sollte sie auch nur dezent eingesetzt werden. Deshalb sollte auch nur auf der obersten Rekursionsstufe eine Ausgabe erfolgen.
# Neue Liste mit einem Element weniger erstellen.
# Aktuelles Element wird entfernt.
nl = l[:]
nl.pop(i)
Jetzt wird eine neue Liste erzeugt, die nicht das aktuelle Element enthält. Ein nl = l führt zu einem falschen Ergebnis, denn die Variablen nl und l würden dann auf die gleiche Liste zeigen. Mit dem Teiloperator [:] ensteht eine tatsächliche Kopie der Liste l, aus der dann das Element entfernt wird. Jetzt kommen wir zur Rekursion. Das aktuelle Element soll mit allen Möglichkeiten der restlichen Elemente verknüpft werden. Und die Kombination der restlichen Elemente liefert uns die Funktion kombiniere(nl).
# Funktion ruft sich selber wieder auf
for c in kombiniere(nl):
# Vor jedes Ergebniselement das aktuelle Element hinzufügen
erg.append(l[i] + c)
Die Funktion kombiniere() wird mit der Liste der restlichen Elemente aufgerufen und liefert eine Liste der Kombinationsmöglichkeiten zurück. Diese wird in die Ergebnisliste erg geschrieben, wobei das aktuelle Element jeweils vor die zurückgelieferte Kombination geschrieben wird.
# Liste aller gefundenen Elemente zurückgeben
return(erg)
Zum Schluss wird dann die Funktion beendet und die erzeugte Liste zurückgegeben.
# Die Liste enthält nur ein Element
else:
return([l[0]])
Wenn die Liste nur ein Element enthält, dann gib einfach das Element zurück. Der Rekursionsast ist damit beendet.
# Hauptprogramm
kombinationen = kombiniere(liste)
Die ganze Rekursion wird durch den Aufruf der Funktion kombiniere(liste) gestartet. Die Ergebnisliste wird in kombination gespeichert.
# Ausgabe der Anzahl der Möglichkeiten und alle Möglichkeiten
print(str(len(kombinationen)) + " Möglichkeiten")
print(kombinationen)
Jetzt noch die Anzahl der Kombinationen ausgeben und natürlich die Liste aller möglichen Kombinationen.
Aber Achtung: Die Anzahl der möglichen Kombinationen steigt sehr schnell an. Daher sollte man mit Ausgabe der Kombinationsmöglichkeiten vorsichtig sein. Bei 10 Elemente besteht die Liste aus über 3 Millionen Elementen. Es dauert extrem lange diese Liste auf dem Bildschirm auszugeben.
Das vollständige Skript
# -*- coding: utf-8 -*-
# ---------------------------------------------
# Alle Kombination von n verschiedenen Elementen
# ---------------------------------------------
# Liste der zu permutierenden Elemente
liste = ["1","2","3","4","5"]
# Funktionen
def kombiniere(l):
# Wenn die Liste mehr als ein Element enthält
if len(l) > 1:
erg = []
# Alle Elemente der Liste bearbeiten
for i in range(len(l)):
# Den Fortschritt nur auf der obersten Ebene anzeigen
if (len(liste) == len(l)):
print(i)
# Neue Liste mit einem Element weniger erstellen.
# Aktuelles Element wird entfernt.
nl = l[:]
nl.pop(i)
# Funktion ruft sich selber wieder auf
for c in kombiniere(nl):
# Vor jedes Ergebniselement das aktuelle Element hinzufügen
erg.append(l[i] + c)
# Liste aller gefundenen Elemente zurückgeben
return(erg)
# Die Liste enthält nur ein Element
else:
return([l[0]])
# Hauptprogramm
kombinationen = kombiniere(liste)
# Ausgabe der Anzahl der Möglichkeiten und alle Möglichkeiten
print(str(len(kombinationen)) + " Möglichkeiten")
print(kombinationen)
Schlagworte: Kombinatorikrekursive Programmierung