Fakultät-Liste

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Peak_me
User
Beiträge: 92
Registriert: Sonntag 27. Januar 2008, 03:09

Hallo!

Es findet ein Autorennen mit 3 Autos statt, bei dem die Autos nebeneinander starten. Ich möchte alle möglichen Startkombinationen ermitteln. (123, 321, 132 etc.)
Eine Liste mit allen möglichen Kombinationen, bei der die Autos auch doppelt starten könnten, ist recht einfach:

Code: Alles auswählen

l=['1','2','3']
kombi=[]
test=[1,0]
for i in range(3):
    for j in range(3):
        for k in range(3):
            kombi=[l[i],l[j],l[k]]
            print kombi
Da kommt dann
111
112
113
211
...
333
bei raus.

Jetzt möchte ich alle Kombinationen, in denen eine Zahl doppelt vorkommt, nicht ausgeben.

Code: Alles auswählen

l=['1','2','3']
kombi=[]
test=[1,0]
for i in range(3):
    for j in range(3):
        for k in range(3):
            kombi=[l[i],l[j],l[k]]
            for m in range(3):
                kombi2=kombi
                kombi3=kombi2
                del kombi3[m]
                if kombi2[m] in kombi3:
                    pass
                else:
                    print kombi
Ich spiele das mal am Beispiel mit der Kombination 121 durch.
kombi ist also gleich 121
also sind
kombi2 und kombi3 auch gleich 121.
Aus kombi3 wird die gerade zu überprüfende Stelle gelöscht; z.B. die erste. Also ist kombi3 = 21.
Wenn nun darin die zu überprüfende Stelle ist (if kombi2[m] in kombi3) soll diese Kombination nicht ausgegben werden; sonst schon.

Erstmal geht das nicht, weil der Index out of range sein soll.
Ich weiß aber nicht warum.

Ich habe mal eine lauffähige Version ausprobiert, die sich aber komplett unlogisch verhält:

Code: Alles auswählen

l=['1','2','3']
kombi=[]
test=[1,0]
for i in range(3):
    for j in range(3):
        for k in range(3):
            kombi=[l[i],l[j],l[k]]
            kombi2=kombi
            kombi3=kombi2
            print kombi2
            del kombi3[0]
            print kombi2
Dabei kommt das raus:
['1', '1', '1']
['1', '1']
...
['3', '3', '3']
['3', '3']

Doch wieso in Gottes Namen?
In diesem Schritt:

Code: Alles auswählen

print kombi2
del kombi3[0]
print kombi2
passiert doch rein garnichts mit kombi2!
Und doch löscht er es nicht nur aus kombi3, sondern auch aus kombi2!
Meine These ist, dass Python spinnt :)


Vielleicht kann mir ja jemand helfen oder hat eine andere Lösung.
Danke schonmal!,
Gruß
peak
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Das liegt daran, das "kombi2" und "kombi3" nur Referenzen auf "kombi" sind und es sich dabei also um die selben Listen handelt (Siehe bei dir die Zeilen 8 bis 10). Um eine (flache) Kopie von "kombi" zu erstellen musst du so vorgehen:

Code: Alles auswählen

kombi=[l[i],l[j],l[k]]
kombi2=kombi[:]
kombi3=kombi2[:]
In Python arbeites du übrigens nur mit Referenzen. Zu Problemen kommt es möglicherweise nur dann, wenn die referenzierten Objekte veränderbar sind.

Edit: Eigentlich würde ich es zwar etwas allgemeiner lösen, aber mir fällt da gerade etwas niedliches ein:

Code: Alles auswählen

[[a,b,c] for a in range(3) for b in range(3) for c in range(3) if len(set([a,b,c]))==3]

Und was hat dein Problem den bitte mit der Fakultät zu tun?! Das sind Permutationen.
Peak_me
User
Beiträge: 92
Registriert: Sonntag 27. Januar 2008, 03:09

Ja, die Gesamtwahrscheinlichkeit ist die Fakultät. Ich wusste aber nicht, wie die Wahrscheinlichkeiten an sich heißen.
Das mit den Referenzen habe ich verstanden.
Ich bin aber nicht so richtig hinter die Funktionsweise deiner Lösung gekommen.

Code: Alles auswählen

[[a,b,c] for a in range(3) for b in range(3) for c in range(3) if len(set([a,b,c]))==3]
print a,b,c
Damit bekomm ich 222 raus.
Oder wie muss ich es richtig machen?
BlackJack

Der Ausdruck baut eine *Liste* auf, die musst Du an einen Namen binden. Die Werte von `a`, `b`, und `c` sind einfach nur die letzten Werte die in der "Schleife" an diese Namen gebunden wurden und sollten Dich nicht weiter interessieren.
xoxox
User
Beiträge: 12
Registriert: Dienstag 11. September 2007, 13:51

Schau dir mal die Beispiele auf http://aspn.activestate.com/ASPN/Cookbo ... ipe/190465 an

Code: Alles auswählen

def xcombinations(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)):
            for cc in xcombinations(items[:i]+items[i+1:],n-1):
                yield [items[i]]+cc

l=['1','2','3']

for xp in xcombinations(l,3): 
    print ''.join(xp)
Ausgabe:
1,2,3
123
132
213
231
312
321
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Hoi,

noch ein Wort zur Mathematik:
Peak_me hat geschrieben:Ja, die Gesamtwahrscheinlichkeit ist die Fakultät.
Ich weiß nicht, um welches Problem es genau geht, aber eine Fakultät *ist* sicher keine Wahrscheinlichkeit.
Peak_me hat geschrieben:Ich wusste aber nicht, wie die Wahrscheinlichkeiten an sich heißen.
Permutationen *sind* ebenfalls keine Wahrscheinlichkeiten.

Wikipedia bietet gute Einführungen in die Begrifflichkeiten.

Wenn Du aber, beispielsweise zur Berechnung einer Wahrscheinlichkeit eines Ereignisses, nur wissen willst *wieviele* Permutationen es für eine best. Menge gibt, so mußt Du nicht zwingend ausrechnen *welche* das sind. Das kann u. U. auch viel Zeit kosten.

HTH,
Christian
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Kürzlich habe ich mein Snippet zur Berechnung von Wortpermutationen aktualisiert, dass es zwar weiterhin rekursiv arbeitet, jedoch `yield` (und damit Generatoren) nutzt. Dadurch war es einfach möglich, alle erzeugten Werte zu sortieren und mehrfache Vorkommen zu eliminieren.

Mit dem Code der rekursiven Funktion bin ich noch nicht zufrieden, aber lesbarer als die Cookbook-Variante dürfte das für dich allemal sein.

OT: Falls jemand da noch einen Kniff zur Abkürzung kennt - ich bin ganz Ohr (meinetwegen auch per PM, wenn es dieses Thema nicht weiterbringt).
Antworten