Um das Problem aus dem Artikel Wieviele Möglichkeiten gibt es zehn Personen auf zehn Plätzen so umzusetzen, dass keiner auf seinem alten Platz sitzt? zu lösen, habe ich erst ein Programm geschrieben, dass alle Möglichkeiten ausprobiert und diese auch anzeigt. Danach habe ich die Folge auf Muster untersucht und die Erkenntnisse daraus sind in die Lösung eingeflossen.
Das in Python geschriebene Skript basiert auf dem Skript aus Artikel Welche Möglichkeiten gibt es 5 verschiedene Elemente unterschiedlich anzuorden?.
# Liste der zu permutierenden Elemente liste = [1,2,3,4,5]
Die fünf Elemente werden durchnummeriert von 1 bis 5 in eine Liste eingetragen. Dies mag zwar im ersten Augenblick etwas umständlich sein, ermöglicht aber später mit dem Skript auch andere Fragestellungen zu beantworten.
# Funktionen def kombiniere(l,stufe):
Die Funktion kombiniere(l,stufe) erledigt die eigentliche Arbeit. Dabei gibt es zwei Situationen für die Funktion. Die Liste i enthält ein Element oder die Liste i enthält mehr als ein Element. Die Variable stufe enthält die Rekursionstiefe und damit auch die Platznummer.
# 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 wird 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.
# Wenn die Zahl der Stufe entspricht, dann ist das Element auf
# seinem alten Platz.
if (l[i] != stufe):
Wenn die alte Platznummer des Elements ungleich der Stufe bzw. der Platznummer ist, dann kann weiter gearbeitet werden.
# 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,stufe+1):
# Vor jedes Ergebniselement das aktuelle Element hinzufügen
erg.append(str(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:
if (l[0] == stufe):
# Letztes Element auf seinem alten Platz => Leere Liste zurück
return ([])
else:
return([str(l[0])])
Wenn die Liste nur ein Element enthält, dann muss natürlich auch noch einmal geprüft werden, ob das letzte Element noch auf seinem alten Platz ist oder einen neuen Platz hat. Daher wird bei einer Übereinstimmung eine leere Liste zurückgegeben und bei keiner Übereinstimmung eine Liste mit dem Element zurückgegeben. Der Rekursionsast ist damit beendet.
# Hauptprogramm kombinationen = kombiniere(liste,1)
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")
if(len(kombinationen) < 400):
print(kombinationen)
Jetzt noch die Anzahl der Kombinationen ausgeben und natürlich die Liste aller möglichen Kombinationen. Da die Anzahl der möglichen Kombinationen sehr schnell ansteigt, wird kommt es nur zu einer Ausgabe, wenn die Anzahl der Kombinationen kleiner als 400 ist. Bei 10 Elemente besteht die Liste aus über 1 Millionen Elementen. Es dauert extrem lange diese Liste auf dem Bildschirm auszugeben.
Bei fünf Elementen gibt es jedenfalls 44 Möglichkeiten.
44 Möglichkeiten ['21453', '21534', '23154', '23451', '23514', '24153', '24513', '24531', '25134', '25413', '25431', '31254', '31452', '31524', '34152', '34251', '34512', '34521', '35124', '35214', '35412', '35421', '41253', '41523', '41532', '43152', '43251', '43512', '43521', '45123', '45132', '45213', '45231', '51234', '51423', '51432', '53124', '53214', '53412', '53421', '54123', '54132', '54213', '54231']
Da die Eingabe durch eine Liste erfolgt, kann man auch andere Fragestellungen mit dem Skript lösen. So kann man die Frage stellen: “Welche Möglichkeiten gibt es 4 Personen auf 5 Sessel umzusetzen, ohne dass eine Person wieder auf ihrem alten Platz sitzt?”
# Liste der zu permutierenden Elemente liste = [1,2,3,4,0]
Für diese Frage wird die Liste so abgeändert, dass das letzte Element zu 0 wird und damit keiner Platznummer entspricht. Übrigens ist es egal, welches Element durch 0 ersetzt wird.
Bei vier Elementen und fünf freien Plätzen gibt es 53 Möglichkeiten für die Anordnung.
53 Möglichkeiten ['21430', '21403', '21034', '23104', '23410', '23401', '23014', '24130', '24103', '24013', '24031', '20134', '20413', '20431', '31204', '31420', '31402', '31024', '34120', '34102', '34210', '34201', '34012', '34021', '30124', '30214', '30412', '30421', '41230', '41203', '41023', '41032', '43120', '43102', '43210', '43201', '43012', '43021', '40123', '40132', '40213', '40231', '01234', '01423', '01432', '03124', '03214', '03412', '03421', '04123', '04132', '04213', '04231']
# -*- coding: utf-8 -*-
# --------------------------------------------------------------------------
# n Elemente sollen so vertauscht werden, dass kein Element auf dem Platz
# mit seiner eigenen Nummer steht.
# --------------------------------------------------------------------------
# Liste der zu permutierenden Elemente
liste = [1,2,3,4,5]
# Funktionen
def kombiniere(l,stufe):
# 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)
# Wenn die Zahl der Stufe entspricht, dann ist das Element auf
# seinem alten Platz.
if (l[i] != stufe):
# 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,stufe+1):
# Vor jedes Ergebniselement das aktuelle Element hinzufügen
erg.append(str(l[i]) + c)
# Liste aller gefundenen Elemente zurückgeben
return(erg)
# Die Liste enthält nur ein Element
else:
if (l[0] == stufe):
# Letztes Element auf seinem alten Platz => Leere Liste zurück
return ([])
else:
return([str(l[0])])
# Hauptprogramm
kombinationen = kombiniere(liste,1)
# Ausgabe der Anzahl der Möglichkeiten und alle Möglichkeiten
print(str(len(kombinationen)) + " Möglichkeiten")
if(len(kombinationen) < 400):
print(kombinationen)