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

Sonntag 14. September 2008, 21:05

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: 2480
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Sonntag 14. September 2008, 21:14

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

Sonntag 14. September 2008, 21:32

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

Sonntag 14. September 2008, 22:16

@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

Montag 15. September 2008, 15:12

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: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Montag 15. September 2008, 15:28

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

Montag 15. September 2008, 15:47

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: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Montag 15. September 2008, 16:52

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

Montag 15. September 2008, 16:58

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

Montag 15. September 2008, 17:47

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: 2480
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Montag 15. September 2008, 18:21

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

Montag 15. September 2008, 18:36

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: 2480
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Montag 15. September 2008, 18:41

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

EDIT2:Schwachsinn...
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Montag 15. September 2008, 18:47

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

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