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:
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:
#include <Array.au3>
$aSymbols = StringSplit("abcde", "", 2)
$aPermute = _ArrayPermute($aSymbols, ",") ; teure Funktion für große |$aSymbols|
_ArrayDisplay($aPermute)
$target = 8
MsgBox(0, "Permute", "[" & $target & "] : " & $aPermute[$target])
Func faculty($n)
$w = 1
For $i = 2 To $n
$w *= $i
Next
Return $w
EndFunc ;==>faculty
Alles anzeigen
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!