Alle Möglichkeiten von (N über M) erzeugen

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
.robert
User
Beiträge: 274
Registriert: Mittwoch 25. April 2007, 17:59

Hallo,

ich habe hier folgende LC

Code: Alles auswählen

m=range(5)
perm = [(a,b,c) for a in m for b in m for c in m]
Dieser erzeugt mir alle 3-Elementigen Permutationen aus einer 5-Elementigen Menge.

So weit so gut.

Aber wie kann ich das ganze mit Parametern versehen, damit die 3 und die 5 eben nicht fest sind, sondern das ich das mit beliebigen Zahlen aufrufen kann?

Jemand eine Idee?

Danke schonmal.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Zum Beispiel so:

Code: Alles auswählen

>>> perm = lambda m,n:eval("[("+",".join(["k%i" %i for i in xrange(n)])+") "+" ".join(["for k%i in xrange(m)" %i for i in xrange(n)])+"]")
>>> perm(2,3)
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
>>> perm(3,2)
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Und wenn die Menge so aussieht:

Code: Alles auswählen

["a", "b", "foo", 7, 12.4]
?

Naja, hier im Board mal suchen und noch googlen, da findet man doch Lösungsansätze zu Hauf!
.robert
User
Beiträge: 274
Registriert: Mittwoch 25. April 2007, 17:59

Hey,

das ging ja fix, danke!

Für mein Vorhaben reicht es wenn die Menge aus Zahlen besteht (lässt sich ja auf alles projezieren), es ist also alles okay.

Nochmals danke!


Grüße,
r.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Hyperion hat geschrieben:Und wenn die Menge so aussieht: ["a", "b", "foo", 7, 12.4] ?
Das ist wohl kaum ein Problem:

Code: Alles auswählen

>>> perm = lambda setM,n:eval("[("+",".join(["k%i" %i for i in xrange(n)])+") "+" ".join(["for k%i in setM" %i for i in xrange(n)])+"]")
>>> perm(["a", "b", "foo", 7, 12.4],3)
[('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'foo'), ('a', 'a', 7), ('a', 'a', 12.4), ('a', 'b', 'a'), ('a', 'b', 'b'), ('a', 'b', 'foo'), ('a', 'b', 7), ('a', 'b', 12.4), ('a', '  - CUT! - 
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Also die Verwenung von "eval" ist eine ganz böse Idee (siehe unzählige Threads)! Eine vernünftige Lösung verwendet Rekursion.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

EyDu hat geschrieben:Also die Verwenung von "eval" ist eine ganz böse Idee (siehe unzählige Threads)! Eine vernünftige Lösung verwendet Rekursion.
Ganz sicher ist eine rekursive Lösung die algorithmisch elegantere, aber deinen pauschalen Verweis auf das "böse eval" und die unzähligen Threads dazu finde ich nicht ausreichend, um meine Lösung als "unvernünftig" zu bezeichnen.

Im konkreten Fall hat der Anwender praktisch keinen Einfluss auf die Konstruktion des eval-Strings - wo also ist das Problem?

Ich hatte auch zunächst mit einer rekursiven Lösung begonnen, bevor die aber fertig war, kam mir die eval-Idee, und ich finde sie gerade darum so interessant, weil sie einmal mehr zeigt, wie flexibel Python ist.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

pütone hat geschrieben:Im konkreten Fall hat der Anwender praktisch keinen Einfluss auf die Konstruktion des eval-Strings - wo also ist das Problem?
Total unlesbar. Code der zur Laufzeit so gebaut wird tendiert dazu, so zu werden. Python hat keine Lisp-Makros, wo sich sowas elegant einfügen lassen würde.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

@.robert: Was du suchst ist übrigens nicht "N über M" sondern das m-fache Kreuzprodukt der Liste. Zumindest sagt das dein Code.

@pütone: Ohne dir jetzt zu nahe treten zu wollen, aber die rekursive Lösung ist in weniger als fünf Minuten geschrieben:

Code: Alles auswählen

def cross(data, m):
    return [[]] if m<1 else [[e]+x for e in data for x in cross(data, m-1)]
Und wo genau braucht man hier jetzt eine "flexible" Lösung mit eval ;-) ?

Und natürlich darf für BlackJack eine Lösung nicht fehlen. Und jetzt lass ich mich überraschen, wie man es mit vorhandenen built-ins lösen kann :) :

Code: Alles auswählen

cross lst m = if m<1 then [[]] else [x:y | x<-lst, y<-cross lst (m-1)]
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Jetzt verschiebt sich aber irgendwie wie Argumentation:

Die - sicher auch subjektiv - schwere Lesbarkeit EINER Zeile Quelltext sehe ich noch nicht als Problem.

@EyDu:
Du bringst keine Argumente, die dein früheres Posting stützen, sondern redest drum herum. Ich habe doch weder behauptet, dass man eine flexible Lösung "braucht", noch dass es lange dauert, eine rekursive Lösung zu entwickeln.

Was an meiner Lösung jetzt "böse" ist, wurde immer noch nicht aufgezeigt. Die schwere Lesbarkeit einer(!) Zeile ist doch wohl noch keine Bösartigkeit.

Ich finde es einfach toll, dass man dieses Problem in Python AUCH so lösen kann.
Benutzeravatar
jens
Python-Forum Veteran
Beiträge: 8502
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Vielleicht hilft das weiter: http://www.python-forum.de/topic-1812.html (Generator für Kombinationen)

GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
BlackJack

@pütone: Ich denke ein ganz grosses Warnzeichen ist Deine Aussage, dass Du die komplizierte Lösung abgebrochen hast, und auf `eval()` zurück gegriffen hast. Das mag vielleicht dogmatisch klingen, aber damit ist diese Zeile für mich schon das personifizierte Schlechte, egal wie sicher oder vielleicht sogar lesbar der Code trotzdem ist. Es ist eine quick'n'dirty Lösung, weil der "offizielle" Weg zu aufwändig war.

Für mich ist `eval()` immer eine Lösung die ausserhalb der Sprache liegt, weil die Sprache dort nicht als interne Objekte, sondern als externe Zeichenkette behandelt wird. Das macht für mich den Unterschied der "Eleganz" bei dynamischen Lösungen aus. Mit `eval()` kann man nicht zeigen, wie flexibel Python ist, sondern gerade, dass man ohne `eval()` auskommen kann, zeigt die Flexibilität der Sprache. `eval()` ist letztlich nichts anderes als Quelltext generieren, etwas, dass man in statischen, unflexibleren Sprachen machen *muss* um Sachen zu erreichen, die in Python prima ohne gehen.
Benutzeravatar
mkesper
User
Beiträge: 919
Registriert: Montag 20. November 2006, 15:48
Wohnort: formerly known as mkallas
Kontaktdaten:

pütone hat geschrieben:Die - sicher auch subjektiv - schwere Lesbarkeit EINER Zeile Quelltext sehe ich noch nicht als Problem.
Viele, die Python benutzen, tun dies, weil hier eben Wert auf Lesbarkeit und Verständlichkeit gelegt wird. Ein obfuscated code contest mag zwar Spaß bringen, fürs Programmieren ist sowas jedoch grundsätzlich ungeeignet.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Außerdem verbaust du mit "eval" jegliche Wartbarkeit des Codes. Es soll ja öfter mal vorkommen, dass man Teile einer Anwendung refactorn muss, was in Python an sich schon relativ schwierig ist. Wenn dann noch Teile des Codes in Strings versteckt sind, wird es vollkommen unmöglich.

Erschwerend kommt dann noch hinzu, dass eine IDE natürlich jegliche Unterstützung and code completion oder sonstigen Features verweigert.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

EyDu hat geschrieben:Außerdem verbaust du mit "eval" jegliche Wartbarkeit des Codes. Es soll ja öfter mal vorkommen, dass man Teile einer Anwendung refactorn muss, was in Python an sich schon relativ schwierig ist. Wenn dann noch Teile des Codes in Strings versteckt sind, wird es vollkommen unmöglich.

Erschwerend kommt dann noch hinzu, dass eine IDE natürlich jegliche Unterstützung and code completion oder sonstigen Features verweigert.
Das ist mal was Handfestes. Ja, verstehe ich.

Im konkreten Fall war es halt so, dass ich auch zunächst mit einer rekursiven Lösung begonnen hatte und mir - zugegeben als jemand, der Rekursion nicht besonders mag - gleichzeitig Gedanken über eine Alternative gemacht habe.
Und da fiel mir das eval() ein - für mich war das ein Aha-Erlebnis, weil ich noch nie vorher die eval()-Funktion in irgendeinem Programm verwendet habe und es einfach interessant fand, das Problem auf diese für mich - im Unterschied zur Rekursion - neue Art und Weise AUCH lösen zu können.

Wie ich ja schon in einem früheren Posting gesagt habe: Die rekursive Lösung ist zweifellos die bessere, keine Frage.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

pütone hat geschrieben:Wie ich ja schon in einem früheren Posting gesagt habe: Die rekursive Lösung ist zweifellos die bessere, keine Frage.
Zumindest bis zum Rekursionslimit. Danach kannst du versuchen sie in eine iterative umzuwandeln oder TailrecursionoptimizedPython zu verwenden.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Wenn man allerdings beim n-fachen Kreuzprodukt das Rekurstionslimit erreicht, dann hat man aber vermutlich ganz andere sorgen :P
Antworten