Bestimmte Permutation bestimmen

  • Hallo zusammen,

    ich habe vor einen klugen Bruteforce-Algorithmus zu schreiben. Der kluge Anteil besteht darin möglichst früh ungültige/schlechte Lösungen zu überspringen.
    Bei den Parametern "a,b,c,d,e" habe ich logischerweise n = 5 => 5! = 120 Möglichkeiten diese zu kombinieren. Vielleicht macht aus irgendeinem Grund "b" an Stelle 1 keinen Sinn, sodass ich viele Berechnungen sparen kann.
    Die Berechnungen sollen weiterhin parallelisierbar sein, also bräuchte ich in dem Beispiel 4 Nodes, die jeweils mit einem anderen Buchstaben anfangen, da das "b" an Stelle 1 ja keine gute Lösung bringt.
    Jede 'Buchstabenkombination' steht exemplarisch für einen Lösungsweg, der ausprobiert werden muss.
    Jetzt zu dem, was mir fehlt:
    Ich brauche eine Funktion, die mir zu einem gegebenen Index die entsprechende Permutation gibt:

    Code
    f(1) := "a,b,c,d,e"
    f(2) := "a,b,c,e,d"
    ...
    f(720) := "e,d,c,b,a"


    Die Baseline ist eine Enumeration aller Möglichkeiten, die in einem Array gespeichert wird. Anschließend kann man per Index auf die entsprechende Permutation zugreifen.
    Das Problem ist, dass bei wachsendem "n" der Speicherverbrauch faktoriell steigt. Bei 4 Nodes will ich dann jedem einen Indexbereich geben, auf dem alles ausprobiert wird.
    Also z.B. bekommt Node1 [1, 144], Node2 bekommt [288, 432], Node3 bekommt [433, 576] und Node4 bekommt [577, 720], weil "b" an Stelle 2 ja ignoriert werden soll.

    Hier ist die Baseline, die leider auf die Enumeration zurückgreift und exemplarisch auf f(8) := "a,c,b,e,d" zugreift, was zu Node1 gehört:


    Vielleicht habt ihr ja kreative Ideen...
    Das Muster, das ich erkannt habe, ist, dass bei den ersten 24 (=(n-1)!) das "a" an erster Stelle steht. Das "b" taucht dann bei den ersten (n-2)! = 6 Permutationen an Stelle 2 auf. "c" steht an (n-3)! = 2 der dritten Stellen. Mit n = |{"a","b","c","d","e"}| = 5.
    Ziel ist es nun einen enigermaßen effizienten Algorithmus zu finden, der das möglichst unter O(n) berechnen kann. Bubblesort n-mal anzuwenden ist nicht gewünscht!

    Ich hoffe, dass ihr ein paar Ideen oder Vorschläge habt! :)

    Wer immer nur das tut, was er bereits kann - wird auch immer nur das bleiben, was er bereits ist!

    Einmal editiert, zuletzt von XovoxKingdom (24. Juli 2017 um 23:40)

  • Hi,
    ich würde nicht nach dem Permute auswerten, sondern schon vorher...
    Schreibe die _ArrayPermute() so um, daß du den einzelnen Symbolen ein "Gewicht" mitgeben kannst, dann wird ArrayPermute nach diesen Gewichten sortieren. Standard wäre bspw "00000"
    Somit hast du, wenn bspw. b schlecht aber e noch schlechter gewichtet wäre (also "01002"), die Permutationen so sortiert, daß die Permutationen von acd "vorne" mit be "hinten" stehen und letztendlich beacd , dann als "schlechtestes" ebacd...
    Was dazu führt, daß du keinerlei Algorithmus benötigst, da die "guten" Permutationen immer vorne, und die schlechten zwangsläufig immer hinten in der Liste stehen.
    Fällt eins oder mehrere Symbole komplett raus, löschst du es aus der Liste komplett.
    Nebenbei kannst du noch eine "Gesamtgewicht"-Funktion mitlaufen lassen, die dir für jede der Permutationen ein "Gesamtgewicht" mitliefert.
    Dann fallen alle Lösungen, welche ein definiertes "Gesamtgewicht" überschreiten, komplett weg!

  • In welchem Universum ist 5! denn 720?

    :whistling: ja, hab teilweise mit 6! gearbeitet. Danke für den Hinweis, aber den Fehler hab ich bei meinen Überlegungen (leider) nicht gemacht, sodass das nicht mein Problem ist.


    Schreibe die _ArrayPermute() so um, daß du den einzelnen Symbolen ein "Gewicht" mitgeben kannst, dann wird ArrayPermute nach diesen Gewichten sortieren

    Ja, kann man sicherlich machen. So hätte ich das Teilproblem gelöst, dass "b" nicht an Position 1 steht. Dennoch muss ich alle Permutationen einmal berechnen und genau das will ich verhindern! ;)

    Ich will eine Funktion, die mir eine Permutation in Abhängigkeit des übergebenen Parameters gibt. Dann kann jeder Node unabhängig voneinander rechnen, die Startpunkte sind äquidistant verteilt und es gibt bis zum Ende keine Dopplungen. Sollte ein Node 'merken', dass seine Permutationen nicht zu einer (guten) Lösung führen, dann kann es mit einer anderen Permutation beginnen, die einem anderen Node zugewiesen wurde, aber noch nicht berechnet wurde.

    Wer immer nur das tut, was er bereits kann - wird auch immer nur das bleiben, was er bereits ist!

  • Ich will eine Funktion, die mir eine Permutation in Abhängigkeit des übergebenen Parameters gibt.

    Aber genau DAS meinte ich doch...
    $array=_ArrayPermuteXXX("abcde","01020") , gibt dir Permutationen zurück, die "ace" an den ersten 3 Stellen verwenden ("gute Lösungen"), b und d kommen IMMer hinten an!


    Sollte ein Node 'merken', dass seine Permutationen nicht zu einer (guten) Lösung führen,

    Programmiertechnischer "Dünnschiss"! :D
    Wenn der Node etwas "merkt" , ist es schon passiert! Denn die "schlechte Lösung" wurde bereits berechnet! ALLE anderen Nodes haben das gleiche Problem! Dann könntest du gleich random durch die Permutationen fliegen und "hoffen", dass möglichst schnell eine "gute" Lösung gefunden wird.
    Was allerdings funktionieren würde wäre eine von allen Nodes erstellte Liste der "schlechten" Lösungen. Über diese Liste lässt man eine "Sortierfunktion" (ich vermute, dass du so etwas suchst) laufen, welche die "schlechteste" Permutation nach vorne holt.
    Nehmen wir an, die Nodes sind "dumm" und fangen an zu rechnen...eine "schlechte" Lösung wird gefunden mit b an der dritten Stelle. Dann wären automatisch ALLE Prermutationen mit b an der dritten Stelle auch "schlecht" (nehme ich an)!? Diese Info wird in die "schlechte" Liste geschrieben ("b3" b an der 3. Stelle ist schlecht)
    Jeder der "dummen" Nodes holt sich die nächste verfügbare Permutation bspw. "caedb" und schaut dann in die Liste..."b3", "c4", "a4"...ok, diese Permutation hat keinen Malus, also berechnen. Bei "cbdae" trifft "a4" und der Node verwirft diese Permutation und holt die nächste verfügbare, bspw. "bcead", rechnet und findet bei "d" eine "schlechte" Lösung. Dann wird der Liste "d5" hinzugefügt....

    Jetzt ist es nur noch eine Frage der aufwendigen Berechnung der Lösungen, ob man über eine wie oben beschriebene Liste die "schlechten" Lösungen ausmaskiert, oder sporadisch ALLE Permutationen durchläuft und die "schlechten" entfernt (wird sich rechentechnisch sicher nicht lohnen).
    Ich vermute mal, die Datenbankspezis könnten hier ein As aus dem Ärmel ziehen und genau diese Permutationen "löschen". Die letztendlich in der DB übriggebliebenen Lösungen wären somit "nicht schlecht".


    Btw. hatte ich vor vielen vielen Jahren mit einem ähnlichen Problem zu tun. Da wurden Fernseher (natürlich mit Röhre! ) produziert und das Bild musste vor der Verpackung des Geräts kalibriert werden. Auf der Platine waren ca. 10 Trimpotis, die alle in irgendeiner Art und Weise Einfluß auf die Bildqualität hatten, und natürlich waren alle Einstellungen voneinander abhängig. "Von Hand" war die Kalibrierung niemals in der Taktzeit (ca. 30 Sekunden) zu schaffen. Also wurde folgendes gemacht: eine Platte mit 10 an Elektromotoren befestigten Schrauberspitzen wurde an die Platine gefahren, und die Elektromotoren fuhren in einer ZUFÄLLIGEN Geschwindigkeit den Einstellbereich des Trimpotis ab. Wie gesagt, jeder Motor hat seinen Trimpoti einfach im gesamten Bereich mehrmals hin und herbewegt. Vor dem Bildschirm saß ein Mitarbeiter mit einem Handtaster und hat das Bild beobachtet. Wenn diese Person nun meinte, das Bild ist "gut", wurde der Handtaster betätigt und der Kalibriervorgang war beendet...nächster Fernseher....der aufmerksame Beobachter wird jetzt fragen was passiert, wenn der "gute" Zustand vom Mitarbeiter nicht erwischt wurde und/oder die Zeit ablief...dann wurde der Bildschirm mit einer SCH*** Bildqualität verpackt.... :D
    Da damals in Barcelona im Werk 24h-Schichten gefahren wurde, kann sich jeder ausrechnen, wieviele LKW mit Fernsehern von dort nach ganz Europa verfrachtet wurden...da kam es auf die Handvoll "Ausschuß" nicht an, denn genau damit haben dann Generationen von sog. "Radio- und Fernsehtechnikern" ihr Brot verdient!

    Was hat jetzt die "Fernseherkalibrierung" mit o.g. Problem, die "beste Lösung" zu finden, zu tun?! Wer DAS begriffen hat, verkürzt die Berechnungszeit auf wenige Prozent/Promille der Berechnungen aller Permutationen!

  • Aber genau DAS meinte ich doch...
    $array=_ArrayPermuteXXX("abcde","01020") , gibt dir Permutationen zurück, die "ace" an den ersten 3 Stellen verwenden ("gute Lösungen"), b und d kommen IMMer hinten an!

    Ich kenne die 'guten' Permutationen zu Beginn nicht! Ich schicke also erstmal alle Nodes mit ihrer Todo-List (=disjunkte Menge an Permutationen) los und lasse sie rechnen.
    Im Laufe der Zeit werden sie merken, dass ihre ihre Lösung nicht gut werden kann und sie Abbrechen.
    Als Abbruchkriterium gilt eine Fehlergrenze epsilon, die zur Terminierung führt.

    Programmiertechnischer "Dünnschiss"!
    Wenn der Node etwas "merkt" , ist es schon passiert! Denn die "schlechte Lösung" wurde bereits berechnet!

    :huh: , was soll das denn? :thumbdown:
    Ich würde es Branch-and-Bound nennen, das ich für eine greedy "variable selection" (machine learning) verwenden will. Der Fehler ja systematisch, sodass ein Abbruch sinnvoll ist!
    Ab einem gewissen Punkt macht es keinen Sinn mehr weitere zu droppen, weil das Modell zu schlecht wird. Aber um die aussagekräftigsten Variablen x[] zu finden, nimmt man erstmal alle und beginnt dann nach und nach welche aus der potenziellen Menge theta[] zu entfernen. Dabei ist logischerweise die Reihenfolge wichtig, da es Interdependenzen gibt.

    Ich habe es nun geschafft eine wie oben beschriebene Funktion zu schreiben, die nicht mit Gewichten arbeitet und so - wie gewünscht - alle Permutationen berechnen muss.
    Falls jemand an der Lösung interessiert ist:

    Spoiler anzeigen

    Der Kern ist die getPermutation Funktion, die ein Array $aArray und einen Wert $v, die die $v-te Permutation zurückgibt.
    Der obere Teil prüft, ob alle Permutationen meiner Funktion auch in _ArrayPermute vorkommen. Die Reihenfolge ist allerdings anders, was mich nicht stört.

    Danke für die Hilfe. Das mit den Gewichten würde sicher funktionieren, aber alle Permutationen aufzulisten und danach zu sortieren - wenn ich dich, Andy, richtig verstanden habe - würde lange dauern.
    Sinnvoll wäre es aber sicher, wenn ich im Vorfeld die schlechten Lösungen kennen würde. Das habe ich anfangs sehr unklar geschildert, wie ich merke X/
    Ich meinte eigentlich, dass ich zu einem beliebigen Zeitpunkt feststellen kann, dass ein Pfad in dem 'Permutationsgraphen' kein Sinn macht und ich den dann abbreche.
    Und das setzt voraus, dass ich zu einem anderen Ast springen kann. Daher die Idee mit dem Index, der mich direkt zu einer anderen Permutation bringt.
    Da meine Funktion eine gewisse Form von Struktur (Sortierung) hat, lassen sich bestimmte Indexmengen sofort ausschließen.

    Wer immer nur das tut, was er bereits kann - wird auch immer nur das bleiben, was er bereits ist!

  • So etwas ähnliches hatte ich mir bereits gedacht.
    Du willst eigentlich nichts weiter, als Nodes aus einem "Baum" abknipsen". Allerdings frage ich mich, wieso du in deiner Funktion GetPermutation() exakt die Funktion ArrayPermute() aufdröselst. Nur "rückwärts"...der Index gibt doch genau die zugeordnete Permutation zurück!?
    Dabei sind die Permutationen an sich völlig uninteressant, da jede sowieso mit einem Index angesprochen werden kann (da die Funktion ArrayPermute() diesen Index vorgibt)
    Somit erübrigte sich auch deine Array-"Rückwärtsberechnung".

    getPermutation($aArray, $v) berechnet extremst aufwendig die Permutation aus einem Index, die du doch sowieso schon berechnet hast bei $Permutation_orginal[$v] ( Local $permutation_orginal = _ArrayPermute($aArray, ""))

    Es stellt sich die Frage, was dir deine Funktion GetPermutation() bringt, außer zum gegebenen Index eine Permutation zurückzugeben...was wie gesagt über den Index sowieso schon erfolgt. ?(


    Sollte bei der Berechnung eine "schlechte Lösung" gefunden werden, bringt es nichts, den dazugehörigen Index zu wissen. Das hatte ich oben schon beschrieben. Elementar ist die Funktion, diese Indizes auszuwerten / zu bewerten. Mal "rechnerisch" gesprochen, deine "schlechte Lösung" wird gefunden, dann MUSS über den Index eindeutig sein, ob die Berechnung der nächsten Permutation überhaupt begonnen wird!
    Die Aussagen "Verwerfe alle Indizes zwischen 49 und 54" und "Verwerfe alle (weiteren) Permutationen, welche mit "cb" beginnen" decken sich! Das eigentliche "Problem", WIE diese Permutationen "abzuknipsen" sind, ist damit nicht gelöst! Natürlich könnte man, wie in deinem Beispiel oben gezeigt, per _Arraydelete() die schlechten (in deinem Fall schon berechneten Lösungen) entfernen. Das mag für die Handvoll Permutationen abcde noch mit Bruteforce möglich sein, bei 8! (abcdefgh) dauert das _ArrayDelete() einer einzigen schlechten Lösung" länger als sämtliche anderen Berechnungen!
    (schau mal HIER, da habe ich die rekursive Fakultät-Funktion gefunden, das ist 6 1/2 Jahre her^^)

    Um zu demonstrieren, was allein bei 8 statt 5 Pfaden rechentechnisch vor sich geht, ersetze "abcde" mit " abcdefgh"

    Es ist definitiv wesentlich einfacher und vor allem schneller, die "schlechten Lösungen" im Orginal-Array entsprechend zu markieren als diese Lösungen komplett aus dem Array zu löschen.
    Ein $permutation_orginal[zu_löschender_index]="" macht diesen Job!