Der Algorithmus geht rekursiv vor:
Angenommen die Zeichenmenge ($pool) sei [a; b; c; d], dann nimmt er sich zuerst das erste Element (hier a) und "hält es fest" ($hold). Dann geht er eine Ebene tiefer und hält das nächte Element fest (hier b), festgehalten wird jetzt also a und b, die Restzeichenmenge ist [c; d]. Sind nur noch zwei Elemente in der Restzeichenmenge (wie hier c und d) werden diese einmal in der normalen Reihenfolge (cd) und einmal in der umgekehrten Reihenfolge (dc) zur Ergebnismenge hinzugefügt, zuvor werden jedoch die festgehaltenen Elemente (ab) vorne angehängt, sodass die Ergebnismenge folgendermaßen aussieht: [abcd, abdc].
Ist eine solche Reihe abgeschlossen springt es zur nächsten und hält dann zunächst b, dann a fest und hängt den Rest wie oben beschrieben an.
Für größere Tiefen, d.h. eine größere Zeichenmenge verläuft das ganze analog, nur dass dann 3 Elemente (z.B. a, b, c) "festgehalten" werden.
Hier ein Ausschnitt des relevaten Code-Teils:
/**
* Permutation (rekursiv)
*
* @author Dominique d'Argent (nicky.nubbel@googlemail.com)
* @param $pool Zeichenmenge, entweder direkt als Array oder als String
* @param $sep Seperator, um die als String übergebene Zeichenmenge aufzuteilen
* @returns array: Alle möglichen Kombinationen der Zeichenmenge
*/
function permutation($pool, $sep = '', $hold = array()) {
// pool-Parameter in ein Array umwandeln
if (!is_array($pool)) {
if (is_string($pool)) {
$pool = $sep ? explode($sep, $pool) : str_split($pool);
}
else {
$pool = (array)$pool;
}
}
// wenn nur noch zwei Elemente übrig sind, z.b. a und b, diese einmal in normaler und
// einmal in umgekehrter Reihenfolge zurückgeben: [ab, ba]
if (count($pool) == 2) {
return array(implode($sep, array_merge($hold, $pool)), // normale Reihenfolge: ab
implode($sep, array_merge($hold, array_reverse($pool)))); // umgekehrte Reihenfolge: ba
}
else {
$res = array();
foreach ($pool as $key => $value) {
$new_pool = $pool;
array_splice($new_pool, $key, 1); // das Element mit dem Index $key aus dem Array löschen
$new_hold = array_merge($hold, array($value)); // den Wert des Elements mit dem Indey $key "festhalten"
$res = array_merge($res, permutation($new_pool, $sep, $new_hold)); // mit der übrigen Zeichenmenge das selbe machen, bis nur noch 2 Elemente übrig sind (s.o.)
}
return $res;
}
}
Eigentlich ganz einfach oder? :-)
Hier noch die Online-Demo: http://dev.ubbel.de/php/permutation/ - die Ergebnisse werden nach der Anzahl der Googletreffer sortiert.
Eigene Zeichenmengen können über die URL übergeben werden, z.B. http://dev.ubbel.de/php/permutation/?pool=nicky - leider ist der Server schon bei recht wenigen Elementen überfordert bzw. braucht sehr lange :-(
Der vollständige Quelltext (live und in Farbe) ist hier zu finden: http://dev.ubbel.de/php/permutation/permutation.phps
ja genau und ich bin der weihnachtsmann! das ist alles andere als einfach, mein lieber freund!
AntwortenLöschen