Alle Kombinationen eine Liste auf 3 andere zu verteilen

Code-Stücke können hier veröffentlicht werden.
Antworten
Benutzeravatar
klaus
User
Beiträge: 88
Registriert: Samstag 23. Juni 2007, 09:33
Wohnort: Kaufbeuren
Kontaktdaten:

Hi,

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)
Wie man an den Variablennamen erkennen kann, geht es hier um Würfel. Man könnte das Problem also auch so formulieren, dass ich alle möglichen Beschriftungen von drei 5-seitigen Würfeln mit den Zahlen 1 bis 15 erhalten will. Logischerweise interessieren mich die Permutationen der Zahlen auf einem Würfel und auch die Permutationen der Würfel selbst nicht.

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(...))
abfangen will, ist result eine leere Liste.

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.
http://klausweidinger.kl.funpic.de
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Ich würd das Grundproblem so angehen:

Code: Alles auswählen

def dump(iterable, i):
    subs = [set()] * i
    while True:
        while all(len(sub) != (len(iterable) // i) for sub in subs):
            # Do sth with subs
        yield subs
        if finished: break
Wenn du mit Mengen statt Listen arbeitest kannst du einfach auf Gleichheit der Mengen testen, da Mengen keine Ordnung haben und du prima alle Zahlen, die noch nicht benutzt wurden, durch die Vereinigungsmenge bestimmen kannst. Natürlich setzt das vorraus, das keine Zahl doppelt im iterable vorkommt, da Mengen Elemente ja unique sein müssen.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

@klaus: Geht es dir in der Hauptsache um das Ergebnis oder um den Algorithmus?

Mit meinem Programm kann ich zwar dein Problem lösen, aber der Code ist so hässlich, dass ich ihn hier lieber nicht zeigen möchte ... :oops:
Er schreit nach Rekursion, aber mein Gehirn widersetzt sich (noch).

Ich habe alle 126.126 Möglichkeiten in eine Datei geschrieben:

Code: Alles auswählen

(1, 2, 3, 4, 5), (6, 7, 8, 9, 10), (11, 12, 13, 14, 15)
(1, 2, 3, 4, 5), (6, 7, 8, 9, 11), (10, 12, 13, 14, 15)
(1, 2, 3, 4, 5), (6, 7, 8, 9, 12), (10, 11, 13, 14, 15)
(1, 2, 3, 4, 5), (6, 7, 8, 9, 13), (10, 11, 12, 14, 15)
(1, 2, 3, 4, 5), (6, 7, 8, 9, 14), (10, 11, 12, 13, 15)
(1, 2, 3, 4, 5), (6, 7, 8, 9, 15), (10, 11, 12, 13, 14)
(1, 2, 3, 4, 5), (6, 7, 8, 10, 11), (9, 12, 13, 14, 15)
(1, 2, 3, 4, 5), (6, 7, 8, 10, 12), (9, 11, 13, 14, 15)
(1, 2, 3, 4, 5), (6, 7, 8, 10, 13), (9, 11, 12, 14, 15)
Die übrigen 126.117 Zeilen erspare ich euch ...

Also, wenn du bloß die Daten brauchst: Bitte melden, kannst du haben.
Benutzeravatar
klaus
User
Beiträge: 88
Registriert: Samstag 23. Juni 2007, 09:33
Wohnort: Kaufbeuren
Kontaktdaten:

Mir geht es vorrangig um das Ergebnis, da ich das für weitere Untersuchungen brauche. Allerdings würde mich der Algorithmus schon auch interessieren, denn auch wenn er "hässlich" ist hat er doch immerhin zum Ziel geführt. (Oder es sieht zumindest so aus, weil die Wahrscheinlichkeit, dass bei einem falschen Algorithmus genau 126126 Ergebnisse rauskommen ist doch relativ gering)
Ich wollte nämlich versuchen, das ganze dann noch allgemeiner zu schreiben und mir ein eigenes Modul für Kombinatorik und Stochastik basteln. Allerdings habe ich bis jetzt noch ein bisschen mit den Algorithmen zu kämpfen und außerdem habe ich bis Dienstag sowieso keine Zeit.

Es wäre nett, wenn du mir den Code und die Datei schicken könntest, falls die Datei nicht zu groß ist. Meine E-mail Addresse ist
klaus|punkt|weidinger|at|vr|minus|web|punkt|de
(ich hoffe, die E-mail findet ihren Weg :P )
http://klausweidinger.kl.funpic.de
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

klaus hat geschrieben:Mir geht es vorrangig um das Ergebnis, da ich das für weitere Untersuchungen brauche. Allerdings würde mich der Algorithmus schon auch interessieren, denn auch wenn er "hässlich" ist hat er doch immerhin zum Ziel geführt. (Oder es sieht zumindest so aus, weil die Wahrscheinlichkeit, dass bei einem falschen Algorithmus genau 126126 Ergebnisse rauskommen ist doch relativ gering)
Das Programm ist mit ziemlicher Sicherheit korrekt im Ergebnis, sonst hätte ich hier nicht gepostet ... :wink:

Ich werde bei nächster Gelegenheit an einer vorzeigbaren Implementation arbeiten (vielleicht postet aber auch jemand anderer noch einen schicken Code, der sich mit rekursiven Algorithmen leichter tut als ich) und diese dann ggf. posten.

Die 126.126 Kombinationen findest du hier (< 400 KB mit bzip2 gepackt): http://home.arcor.de/zahnkranz/material/15auf3.txt.bz2
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Hier wäre meine Lösung:

Code: Alles auswählen

def triples(pool):
    result = set()
    pool = frozenset(pool)
    for p1 in combinations(pool, 5):
        p1 = frozenset(p1)
        rest = pool - p1
        for p2 in combinations(rest, 5):
            p2 = frozenset(p2)
            result.add(frozenset((p1, p2, rest - p2)))
    return result
Braucht das neue "combinations" aus itertools in 2.6.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Benutzeravatar
klaus
User
Beiträge: 88
Registriert: Samstag 23. Juni 2007, 09:33
Wohnort: Kaufbeuren
Kontaktdaten:

Wenn ich das richtig verstehe hast du einfach alle Möglichkeiten berechnet, 5 Zahlen aus 15 auszuwählen und dann im 2. Schritt 5 Zahlen aus dem Rest.
Daran habe ich auch gedacht, nur wusste ich nicht genau, wie ich das umsetzen soll.
Nochmals danke für die Lösungsansätze und die fertige Liste mit allen Möglichkeiten. Was mich aber trotzdem noch interessieren würde ist, warum mein Code nicht funktioniert hat und wo mein Denkfehler liegt.
http://klausweidinger.kl.funpic.de
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Mein Programm ist im Prinzip genauso aufgebaut wie das von birkenfeld, wobei ich zusätzlich an den entscheidenen Stellen Sets in Tupel (und umgekehrt) konvertiert habe, um am Ende eine Liste aller Möglichkeiten zu haben, die einigermaßen sinnvoll sortiert ist.

Hauptunterschied ist der, dass ich an Stelle der mir bis dahin unbekannten Funktion combinations() eine eigene Funktion geschrieben habe, und eben die ist "hässlich", weil sie fünf geschachtelte for-Schleifen enthält und eigentlich rekursiv umgesetzt werden müsste.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

@klaus:

Du setzt das Statement yield ein. Dadurch wird nicht der Wert zurückgegeben, sondern ein Generator erzeugt, der dann zurückgegeben wird und über den man iterieren kann. Du erzeugst rekursiv weitere Generatoren, schmeißt sie aber gleich wieder weg. list() versucht dann über den Generator der Hauptfunktion zu iterieren. Das einzige yield Statement wird aber von der if Bedingung am Anfang überdeckt, wodurch nichts generiert wird. Folge ist ein leerer Generator, aus dem list dann eine leere Liste erzeugt. Für genaueres siehe Tutorial / Language Reference.
Benutzeravatar
klaus
User
Beiträge: 88
Registriert: Samstag 23. Juni 2007, 09:33
Wohnort: Kaufbeuren
Kontaktdaten:

OK, ich gebe zu, ich habe yield noch nie in einem eigenen Programm verwendet und deshalb habe ich es wahrscheinlich nicht richtig eingesetzt. Wenn ich das jetzt richtig verstanden habe gibt yield zwar den Wert zurück, allerdings nur an die nächsthöhere Blockstruktur. Ich versuche Mal, das ganze so umzuschreiben, dass es klappt.
http://klausweidinger.kl.funpic.de
Benutzeravatar
klaus
User
Beiträge: 88
Registriert: Samstag 23. Juni 2007, 09:33
Wohnort: Kaufbeuren
Kontaktdaten:

edit: Im falschen Topic gepostet.
Zuletzt geändert von klaus am Montag 27. Oktober 2008, 20:58, insgesamt 1-mal geändert.
http://klausweidinger.kl.funpic.de
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

klaus hat geschrieben:Wenn ich das jetzt richtig verstanden habe gibt yield zwar den Wert zurück, allerdings nur an die nächsthöhere Blockstruktur.
Nein, es ist wie ein ``return``, nur dass die Funktion dann nicht endet, sondern von Außen mit ``.next()`` fortsetzen kann: sie laufen nach dem ``yield`` dann direkt weiter, bis zum nächsten ``yield`` oder ``return``.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Benutzeravatar
klaus
User
Beiträge: 88
Registriert: Samstag 23. Juni 2007, 09:33
Wohnort: Kaufbeuren
Kontaktdaten:

So habe ich mir das bis jetzt auch immer gedacht. Aber das hieße doch, dass ich die Ergebnisse, die mir yield ausspuckt mit list() auffangen können müsste. Wenn ich das versuche erhalte ich aber immer eine leere Liste. Wo ist denn dann mein Denkfehler?
http://klausweidinger.kl.funpic.de
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

?

Durch den Aufruf einer Generator Funktion wird nicht *direkt* ein Wert zurückgegeben (also auch nicht nacheinander, wie bei "mehreren returns", würde das gehen), sondern ein Generator *Objekt*. Das Objekt ist dann "iterable" und hat eine next() Methode. Du kannst es zb in einer for-schleife einsetzen. Wenn du das *Objekt* aber an nichts bindest, wird es weggeschmissen.

Und wenn du eine Bedienung benutzt, die *nie* erfüllt wird, nirgendwo sonst "yield" benutzt wird, wird auch nichts "geyieldet". Also ist das ZUrückgebene Objekt leer. (Wie eine leere Liste, ist ja auch ein Containerobjekt).
Luecx
User
Beiträge: 15
Registriert: Dienstag 4. März 2014, 12:16

import itertools und mit list(itertools.permutations([A,B,C,D])) kannst du alle kombinationen wiedergeben, habs nur kurz ausprobiert. Aber es sollte eigentlich klappen
BlackJack

@Luecx: Schau mal auf das alter von diesem Thema. Mit `permutations()` bekommt man nicht die Kombinationen sondern wie der Name schon sagt, die Permutationen. Und Permutationen sollten explizit nicht das Ergebnis sein — Zitat aus dem ersten Beitrag: „[…] das heißt mich interessieren keine Permutationen.”
Antworten