Permutation in PHP -- Alle Kombinationen eines Arrays finden

<?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";

?>

231

321

132

312

123

213

<pre><?php print_r( permutation( array( 'T', 'D', 'I' ) ) ); ?></pre>

<?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;

	}

}

?>