Willkommen in der Webstatt Zum Webstatt Blog und Stories
milahu milahu am 31.05.06 00:01

Um ein mathematisches Problem per Burte-Force zu lösen (Ich weiß, ich bin denkfaul), benötigte ich Permutation (Alle möglichen Kombinationen einer Liste).
Da ich aber nichts für mich passendes gefunden habe, musste eine eigene Funktion her. Und hier ist sie:

<?php

function permutation($list, $clean = true) {
// Das Nirvana fuer kommende Permutanten
$res = array();

// Elemente der Liste durchlaufen
for ($i = 0; $i < count($list); $i++) {

$_list = $list;

// Ein Element ausschneiden ...
list($elm) = array_splice($_list, $i, 1);

$_res = $_list;

// ... und an's Ende anhaengen
array_push($_res, $elm);

// Ab in's Nirvana!
$res[] = $_res;

// Dieses Ergebnis weiter permutieren -- allerdings
// ohne das vorhin wieder angehaengte Element ...
$perm = permutation($_list, false);

// ... welches wir nun wieder anhaengen
foreach ($perm as &$p) {
if (is_array($p)) // Ergebnisse?
array_push($p, $elm);
}

// Neue Permutationen an's Nirvana anhaengen
$res = array_merge($res, $perm);
}

// Duplikate loeschen
if ($clean) {
// Arrays zu Strings konvertieren, um dann ...
foreach ($res as &$r)
$r = serialize($r);

// ... vergleichen zu koennen ...
$res = array_unique($res);

// ... und wieder zu Arrays zu konvertieren
foreach ($res as &$r)
$r = unserialize($r);
}

return $res;
}

// Was waere eine Funktion ohne ein Beispiel..? ;-)
$perm = permutation(range(1, 3));
foreach ($perm as $p)
print implode('', $p)."\n";
?>


Ausgabe:
231
321
132
312
123
213


Eine kurze Beschreibung von dem, was passiert:
Es wird immer ein Element der Liste ausgeschnitten und an's Ende angehängt. Dadurch entsteht eine neue Mutation. Diese muss jedoch wiederum mutiert werden. Dazu wird zunächst das letzte Element (das ja schon vorher "durchmutiert" wurde) entfernt, die übrigen Elemente werden mutiert und schließlich wird der vorher abgeschnittene Teil an die neu entstandenen Mutationen angefügt.
Zum Schluss werden noch Duplikate entfernt, denn das Skript würde so n^n Mutationen finden, wobei es nur n! (Fakultät) gibt.

PS: Hoffentlich kann das jemals wer brauchen ;)

Anmerkung: Wer einen String per Zufall mischen lassen will, möge auf die Funktion str_shuffle() zurückgreifen. ;)

netcup.de Warum gibt es hier Werbung?
milahu milahu am 02.06.06 15:02

Ein Einzeiler für den Moloch ;)
<pre><?php print_r( permutation( array( 'T', 'D', 'I' ) ) ); ?></pre>
Den Algorithmus hab ich übrigens von hier abgekupfert und natürlich verbessert.. ;)

Hier ist übrigens die Denksportaufgabe ("Walbendinger Zahlenkreis") zu finden, die ich mit folgender Kanone erlegt habe :D

<?php

/*
* Walbendinger Zahlenkreis
* 720 Kombinationsmöglichkeiten -- Wir suchen eine davon!
* Quelle: Die Zeit <http://www.zeit.de/2006/22/Spiele_2fLogelei_22>
*/

// Farben
$farbe = array(
'rot',
'gelb',
'gruen',
'orange',
'blau',
'violett'
);

// Funktionen
$funktion = array(
array('a', '$x * 2 - 102'),
array('b', '$x / 5 + 91'),
array('c', '$x + 13'),
array('d', '$x / 2 + 43'),
array('e', '$x - 9'),
array('f', '$x * 3 - 188')
);

// Felder des Kreises
$feld = array(
// Farbe, Ziffernanzahl
array(0, 1), // Startfeld
array(1, 2),
array(2, 2),
array(3, 2),
array(4, 2),
array(0, 2),
array(1, 2),
array(4, 3),
array(0, 2),
array(2, 3),
array(5, 3),
array(4, 2),
array(2, 2),
array(4, 2),
array(4, 2)
);


foreach (permutation(range(0,5)) as $kombi) { // 6! Kombi's: Farbe -> Funktion


// Startzahl (muss in Startfeld passen)
for ($_x = 1; $_x <= 9; $_x++) {
$x = $_x;
$passt = true;

// Kreis durchlaufen
$kreis = null;
foreach ($feld as $f_id => $f) {
list ($f_farbe, $f_ziffern) = $f;
$f_id = $kombi[$f_farbe];
list ($f_fname, $f_fterm) = $funktion[$f_id];

if ($f_ziffern != strlen("$x")) { // Zahl passt nicht ins Feld!
$passt = false;
break;
}

eval('$y = '.$f_fterm.';');

$kreis .= "{$farbe[$f_farbe]}: $f_fname($x) = $y\n"; // Fuer spaeter ...

$x = $y;

if ($x <= 0) {
$passt = false;
break;
}
}

// Treffer!
if ($passt)
print "Treffer!\n".$kreis;
}
}
?>

Creative Commons Lizenzvertrag
Alle Inhalte des Webstatt-Archivs stehen unter einer Creative Commons Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Unported Lizenz.

Impressum & Kontakt