Das deutsche Python-Forum

Hallo!

Hab mal wieder ein Problem... Ich würde gern aus einer Liste mit n Sublisten jede mögliche Reihenfolge durchprobieren lassen, um dann anschließend eine qualitative Aussage über die beste "Möglichkeit" treffen zu können.

Beispiel:

Aus: wird: Mein Problem ist, dass ich n Einrückungen für n for-Schleifen bräuchte. Ich weiß nicht wie ich das umsetzen soll.

Ein weiteres Problem ist meiner Meinung nach die Speicherauslastung... Bei jenseits von n=20 wären es schon über 2,4 Trillionen Ergebnisse, die miteinander verglichen werden müsssten.

Was du suchst ist Rekursion.

Speicher wird da nicht ausgelastet (außer du speicherst natürlich alle Ergebnisse), das hängt lediglich von der Rekursionstiefe ab. Nur die CPU wird sich über die ganze Arbeite freuen... Vielleicht solltest du genauer beschreiben, was du vor hast. Ab gewissen n/m ist es praktisch einfach nicht mehr möglich alle Kombinationen zu testen. Und diese Grenze ist sehr schnell erreicht.

@Daniel_SGe: Um's mal zu verdeutlichen: Bei n=20 und nur einer Nanosekunde pro Test, bräuchte das Programm 77 Jahre.

Hi!

Im Prinzip versuche ich (hat indirekt etwas mit meinem vorherigen Thread zu tun) die beste Reihenfolge der Elemente der Liste zu finden, so dass der resultierende Funktionswert am geringsten ist. Das, was ich in meinem voherigen Thread versucht hatte zu klären erlaubt ja nur kurzfristige Vorhersagen.

Da die Anzahl der Elemente in der Liste variabel sind, könnte man eventuell für niedrige n (bei einer Nanosekunde pro Test zwischen 14 und 15) eine exakte Berechnung vornehmen, wohingegen für höhere n nur die ersten 3-5 Reihenfolgen der Elemnte exakt bestimmt werden also : n! / (n-3)! und für die restlichen die Näherung aus meinem vorherigen Thread verwendet wird.

Wichtig wäre es dafür eben auch zu wissen, wie lange eine solche Testprozedur pro Test dauert. Gibt es dafür Richtwerte? Oder einfach nur durch Messen mit mittelgroßen n?

Wie lange ein bestimmter Test dauert kannst du nur rausfinden, indem du den Mittelwert über mehrere Tests nimmsts. Das wird von Rechner zu Rechner variieren. Nur die Anzahl der durchzuführenden Tests kannst du vorher genau bestimmen.

Gibt es eventuell eine günstige Konstellation der Daten, so das man in etwa vorraussagen kann, welche Reihenfolge ein gutes Ergebnis liefert? Falls es die Daten erlauben, dann könntest du solch ein approximatives Verfahren noch mit Gradientenabstieg verfeinern. Wie schlecht die Näherung im schlimmsten Fall werden kann müsste/sollte man dann natürlich noch bestimmen.

Ja, es gibt Konstellationen, die besonders günstig sind. Die einzelnen Werte werden noch mit einem weiteren Wert verknüpft, der umso größer wird , je höher Diff(index.liste) ist...

am günstigsten wären also werte, die sagen wir mal max 10% vom eigentlichen Minimum abweichen und kombiniert eine Diff(index.liste) von maximal 0,2*n hat.

Was sind denn Vorraussetzungen dafür, dass ich den "Gradientenabstieg" verwenden darf?

Prinzipiell kannst du das Gradientenabstiegsverfahren immer anwenden, wie gut es in einem konkreten Fall ist muss man einfach mal testen.

Schlechte Vorraussetzungen für das Verfahren sind natürlich Daten, die extrem viele Sprünge aufweisen, beispielsweise wenn alle Werte im Raum mit einem zufälligen Wert belegt sind. Dann landet man viel zu schnell in einen lokalen Minimum.

Wenn du dich nicht groß um Approximationen kümmern willst, würde ich zunächst k zufällige Punkte (Kombinationen) nehmen und für diese dann den Abstieg versuchen. Vielleicht reicht Dir diese Genauigkeit ja schon aus und du gannst ab und zu eine größere Abweichung vom Minimum vertragen. Das lässt sich auch alles relativ schnell und einfach programmieren.

Wenn du dann nicht zufrieden bist kannst du immer noch Zeit in die Vorgeschlagene Approximation investieren. Der Beweis einer gewissen Genauigkeit, um diese zu garantieren, wird allerings recht aufwändig werden.

``itertools.permutations()`` in 2.6?

Okay, werd ich mir erstmal anschauen, inwiefern das notwendig sein wird.
@Y0Gi: was?^^

Und: Ich google grad schons eit ner halben Stunde. Gibt es eine Möglichkeit, dass wenn ich einen Wert einer for Schleife (for a in b) b verändere, dass diese Änderung beim nächsten Durchlauf derselben Schleife quasi zurückgesetztt wurde. Ansonsten kann man das ganze mit rekursiv in dem Fall glaub ich vergessen, bzw. es würde unnötig kompliziert...

Daniel_SGe hat geschrieben:Gibt es eine Möglichkeit, dass wenn ich einen Wert einer for Schleife (for a in b) b verändere, dass diese Änderung beim nächsten Durchlauf derselben Schleife quasi zurückgesetztt wurde.

Nein.

Na toll... Aber sowas wär doch eigentlich wichtig. Sind solche Aufgabenstellungen dann grundsätzlich nicht lösbar oder muss man sich eben ein "workaround" basteln?

Ich würds ja mal mit ner while Schleife probieren

EDIT2:Schwachsinn...

Daniel_SGe hat geschrieben:Gibt es eine Möglichkeit, dass wenn ich einen Wert einer for Schleife (for a in b) b verändere, dass diese Änderung beim nächsten Durchlauf derselben Schleife quasi zurückgesetztt wurde.

Wie meinst du? Das im aktuellen Lauf ``b`` anders ist als im nächsten, wo es wieder das ursprüngliche ``b`` ist?

Ja, genau... Im aktuellen Lauf verändert sich der (Ursprungs-)Wert von b... Ich möchte ja für kleine n erst einmal alle Möglichkeiten durchprobieren... Der Wert b muss dann natürlich für die oberste Ebene bei jedem Listenelement wieder der gleiche sein...

Dann kopier eben im Schleifenkörper ``b`` in, sagen wir mal ``c`` und modifiziere es. Das wird dann in der nächsten Iteration verworfen und du hast wieder dein ursprüngliches ``b``.

hmmm... also wenn ich b kopiere (c=b) hab ich dasselbe Problem wieder... vll. ist ja nicht ganz irrelevant, dass die schleife nur indirekt von b abhängt (nämliche eigentlich for a in f(b, d))...

Die Schleife sieht im Moment so aus: Diese Änderung von c bleibt auch beim nächsten Durchlauf...

*Achtung*: Bei ``c = b`` wird nichts kopiert, sondern einfach nur der Name `c` an das selbe Objekt gebunden, an das auch `b` gebunden ist! Du hast dann immer noch nur *ein* Objekt, das halt über die beiden Namen ansprechbar ist.

Okay, Danke!

Das funktioniert jetzt...

Hab aber nun ein weiteres Problem:

Ich möchte meine Ergebnisreihe, die ich nun erhalte natürlich auch auswerten und schließlich auf die richtige Reihenfolge schließen können.
Dies wäre am einfachsten wenn eine liste "folge" für jede Ebene auch um eine neue Unterebene erweitert werden würde...
Also für die dritte Ebene: als Ergebnis rausstellen sollte, müsste ich schließlich nur doch die funktionswerte für die jeweiligen schritte angeben...

Ich stolper im Moment darüber, dass ich mit folge[x].append(bla) nur die oberste ebene erreiche. Ist es möglich [x] in abhängigkeit von der Ebene zu betrachten?... (z.b. folge[x1][x2])

keiner eine Idee?...

Ich wüsste sonst nicht, wie ich das ganze auswerten soll... Reih ich die Listen einfach normal aneinander erhalte ich pro Rekursionstiefe (n-1) nicht eine Liste der Länge n!*n, sondern etwas weniger... Damit lässt sich eben wenig anfangen... Daher die idee mti den verschachtelten Listen...