ich versuche gerade ein Programm zu schreiben, dem ich eine Liste von 15 Zahlen und drei leere Listen übergebe, und das mir dann alle Möglichkeiten ausgibt, die Zahlen so auf die drei leeren Listen zu verteilen, dass in jeder genau 5 Elemente sind. Dabei soll das Programm nur wirklich verschieden Möglichkeiten ausspucken, das heißt mich interessieren keine Permutationen.
Soll heißen:
[[1,2,3],[4,5,6]] und [[3,1,2],[5,4,6]] und [[4,5,6],[1,2,3]] sind das gleiche und es soll nur eine dieser Möglichkeiten ausgegeben werden, wenn möglich die erste.
Mein bisheriger Ansatz ist rekursiv und sieht so aus:
Code: Alles auswählen
import copy
def dice_dist(dice, spots):
if len(spots) == 0:
yield dice
else:
flag = False
if len(dice[0]) < 2:
limits_die = 0
flag = True
elif len(dice[1]) < 2:
limits_die = 1
flag = True
elif len(dice[2]) < 2:
limits_die = 2
flag = True
if flag and len(dice[limits_die]) == 0:
w_dice = copy.copy(dice)
w_spots = copy.copy(spots)
w_dice[limits_die].append(w_spots.pop(0))
dice_dist(w_dice, w_spots)
elif flag:
for x in range((dice[limits_die][-1]-len(dice[limits_die])),(len(spots)-len(dice[limits_die]))):
w_dice = copy.copy(dice)
w_spots = copy.copy(spots)
w_dice[limits_die].append(w_spots.pop(x))
dice_dist(w_dice, w_spots)
Der Lösungsansatz ist dabei, dass ich die Würfel nacheinander beschrifte, d.h. erst Würfel 1, dann Würfel 2, dann Würfel 3. Dabei sucht das Programm zuerst den ersten Würfel aus, der noch nicht voll beschriftet ist, und fügt dann eine neue Zahl hinzu, die dann aus "spots" (Vorrat der noch verbleibenden Augenzahlen) entfernt wird. Wenn der nächste Würfel angefangen wird (z.B. wenn Würfel 1 voll ist) wird die 1. noch verbleibende Zahl in "spots" auf diesen Würfel geschrieben, um zu garantieren, dass die Würfel nach ihrer niedrigsten vorkommenden Augenzahl sortiert sind. Wenn der Würfel aber schon eine Zahl enthält, werden alle restlichen Zahlen von "spots" nacheinander mit einer for-schleife auf ihn verteilt. Dabei sind die Grenzen der for-Schleife so gewählt (wenn ich keinen Denkfehler gemacht habe), dass die Zahlen auf einem Würfel immer in aufsteigender Reihenfolge sortiert sind.
Bis jetzt gibt mir das Programm leider nichts zurück, d.h. wenn ich die Ergebnisse mit
Code: Alles auswählen
result = list(dice_dist(...))
Die Funktion copy benötige ich, damit die Vorgänge einem Durchlauf der for-Schleife nicht die im nächsten Durchlauf beeinflussen.
(Theoretisch müsste es 126126 verschiedene Kombinationen geben.)
Wäre nett, wenn mir jemand helfen könnte.