Funktion mit n! verschiedenen Möglichkeiten durchführen

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.
Daniel_SGe
User
Beiträge: 28
Registriert: Montag 8. September 2008, 19:39

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:

Code: Alles auswählen

Liste[[a]+[b]+...+[n]]
function(n, m)
wird:

Code: Alles auswählen

for n in liste:
  function(n, m)
  "Parameteränderung von m"
  del liste[n]
  for n in liste:
     function(n, m)
    "Parameteränderung von m"
    del liste[n] 
    ...
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.
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Was du suchst ist Rekursion.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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.
BlackJack

@Daniel_SGe: Um's mal zu verdeutlichen: Bei n=20 und nur einer Nanosekunde pro Test, bräuchte das Programm 77 Jahre.
Daniel_SGe
User
Beiträge: 28
Registriert: Montag 8. September 2008, 19:39

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?
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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.
Daniel_SGe
User
Beiträge: 28
Registriert: Montag 8. September 2008, 19:39

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?
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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.
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

``itertools.permutations()`` in 2.6?
Daniel_SGe
User
Beiträge: 28
Registriert: Montag 8. September 2008, 19:39

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...
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

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.
Daniel_SGe
User
Beiträge: 28
Registriert: Montag 8. September 2008, 19:39

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?
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Ich würds ja mal mit ner while Schleife probieren ;)

EDIT2:Schwachsinn...
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

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?
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Daniel_SGe
User
Beiträge: 28
Registriert: Montag 8. September 2008, 19:39

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...
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

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``.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Daniel_SGe
User
Beiträge: 28
Registriert: Montag 8. September 2008, 19:39

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:

Code: Alles auswählen

for a in f(b, d)
  c = b
  do ...
 c[a]=[]
Diese Änderung von c bleibt auch beim nächsten Durchlauf...
BlackJack

*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.
Daniel_SGe
User
Beiträge: 28
Registriert: Montag 8. September 2008, 19:39

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:

Code: Alles auswählen

folge = [a, [a, [a , b], b, [a, b]], b[...]]
Wenn sich
folge[1][1][0] 
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])
Daniel_SGe
User
Beiträge: 28
Registriert: Montag 8. September 2008, 19:39

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...
Antworten