Problem mit Auflistungen/Permutationen

[hoppelchen]

Hi,

ich hab mir in den Sinn gesetzt, alle Möglichkeiten auszugeben, wie man k Zahlen auf n Stellen verteilen kann. Dabei wäre mir die Reihenfolge wichtig, jedoch sollen keine Wiederholungen vorkommen. Dabei möchte ich k und n selbst variabel bestimmen können (für nen festen wert hab ichs mit entsprechend vielen schleifen gelöst)

Mein Ansatz, das ganze über Rekursionen zu basteln läuft auf den ersten Anschein gut durch, allerdings finden sich einige doppelte Kombinationen. Nun meine Frage: wie könnte man das besser lösen?

Code: Alles auswählen

import numpy
zahlen = set(range(0,3))
anzahl_stellen = 3
Reihenfolge = numpy.zeros(anzahl_stellen)
count = 0 # dient zur kontrolle (anzahl der Kombinationen kann man ja leicht über n! / (n-k)! ausrechnen)

def perm(zahlen, anzahl):  
    if len(zahlen) < anzahl:
        print "Geht nicht..."
        return 0  
    if anzahl-1 >=0:
        for i in zahlen:
            Reihenfolge[anzahl-1]=i      
            perm(zahlen, anzahl-1) 
            if len(set(Reihenfolge)) == anzahl_stellen: # sortiert Kombinationen aus, die Mehrfachnennungen von Zahlen beinhalten
                global count
                count += 1
                print Reihenfolge       
   

perm(zahlen, anzahl_stellen)
print count

liefert bei mir

Code: Alles auswählen

[ 2.  1.  0.]
[ 2.  1.  0.]
[ 1.  2.  0.]
[ 2.  0.  1.]
[ 2.  0.  1.]
[ 0.  2.  1.]
[ 1.  0.  2.]
[ 0.  1.  2.]

Dabei sind offensichtlich ein paar Kombinationen zuviel dabei. Habe die Idee, alle Kombinationen zu speichern und dann eine Abfrage darauf zu machen, ob eine Kombination neu ist, wieder verworfen - wird dann richtig böse vom Speicher her bei größeren Werten für k und n.
Bin momentan wieder etwas ratlos und für Ideen und Verbesserungsvorschläge aller Art aufgeschlossen.

Danke euch schonmal

[EyDu]

Hallo,

wenn du es nicht als Übung machst, dann kommst du so an das Ergebnis: http://docs.python.org/library/itertool ... rmutations. Dort steht auch der dazugehörige Code.

Edit: Du solltest bei den Code-Tags als Sprache noch python angeben, dann kann man es vernünftig lesen.

Code: Alles auswählen

...

Sebastian

[hoppelchen]

Ahja, cool. Danke.

edit: allerdings würde ich die ergebnisse noch etwas weiter verarbeiten wollen (insbesondere zu Testzwecken abspeichern und ein wenig damit rumrechnen). Und da tu ich mich mit dem itertools-ansatz etwas schwer...

[EyDu]

Dann zeig doch mal, wo es noch Probleme gibt. Das anzupassen ist meist einfacher, als auf Funktionen aus der Standardbibliothek zu verzichten.

[hoppelchen]

Sagen wir mal so: wenn ich die einzelnen Kombinationen in Arrays vorliegen hätte und darauf zugreifen könnte, dann wäre ich happy. Und darin liegt das Problem, da ich den Code noch nicht wirklich nachvollziehen kann. Bin da immer noch am reindenken...

Ist das wirklich so schwer, das ohne Funktionen aus der Standardbibliothek hinzubekommen? Ich habs ja schon fast

[EyDu]

Hallo.

Schwer ist es nicht, aber umständlicher und fehleranfälliger.

Suchst du das?

Code: Alles auswählen

>>> import itertools
>>> list(itertools.permutations(range(3), 3))
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

Sebastian

[hoppelchen]

Hab ich schon gefunden. Problem dabei ist wie gesagt, dass ich alles als liste vorliegen habe.

Angenommen, ich wollte die Summe der einzelnen listenelemente berechnen lassen, also 0+1+2=3, usw.
Daran hakts bei mir, also beim Zugriff auf die Werte der einzelnen "arrays".

[BlackJack]

@hoppelchen: Das sind aber wirklich absolute Python-Grundlagen wie man Listen verarbeitet.

Code: Alles auswählen

In [137]: ps = list(permutations(xrange(3), 3))

In [138]: ps
Out[138]: [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

In [139]: [sum(p) for p in ps]
Out[139]: [3, 3, 3, 3, 3, 3]

In [140]: ps[0]
Out[140]: (0, 1, 2)

In [141]: ps[1]
Out[141]: (0, 2, 1)

In [142]: for p in ps:
   .....:     print p
   .....: 
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)

Das sollte man nach dem Durcharbeiten eines Tutorials drauf haben.

[EyDu]

Meinst du so etwas:

Code: Alles auswählen

>>> import itertools
>>> data = list(itertools.permutations(range(3), 3))
>>> [sum(x) for x in data]
[3, 3, 3, 3, 3, 3]
>>> for x in data:
...     print sum(x)
... 
3
3
3
3
3
3

Wenn es daran scheitert, dann solltest du unbedingt das Python-Tutorial durcharbeiten

Sebastian

Edit: Da war ich wohl zu langsam

[hoppelchen]

*In die Ecke stell und schäm*
Jo, denn geht das. Danke euch beiden...

edit: Tutorials mag ich in Regel nicht. Ich übe lieber an konkreten Beispielen wie oben - auch wenns etwas schmerzhafter ist und man sich öfter blamiert und mehr blöde fragen stellt

Trotzdem: falls jemand ne Möglichkeit hat, meinen Code doch noch zum richtigen Ergebnis zu bewegen, dann wärs spitze. Standardbibs hin oder her: ich mach gern was selbst - da weiß ich, was ich gemacht hab (und dann passiert mir auch der FauxPas mit den Listen nicht)

Danke euch beiden nochmals

[EyDu]

An Beispielen lernen ist nicht verkehrt, aber das Standard-Tutorial solltest du in jedem Fall durcharbeiten. Es ist relativ kurz und alle wichtigen Dinge werden kurz angerissen. Du kommst so wesentlich effizienter zu besseren Lösungen, da du deine Zeit nicht mit solchen Kleinigkeiten wie for-Schleifen verschwendest.

Das Nachimplementieren von Funktionalität ist zur Übung sicher auch nicht schlecht, wenn du den Code einsetzt solltest du jedoch immer das bereits vorhandene nutzen. Ziel sollte es nicht sein, möglichst viel Code zu schreiben, sondern vorhandenen Code zu nutzen um deine eigenen Ideen umzusetzen. Das bringt auch viel mehr Spaß als irgendwelchen Standardkram runter zu programmieren