[php] Algorithmus Kombinatorik

[Valmont]

Hallo zusammen,
es geht um eine Darstellung von Positionen in einer "Firma" für ein Game-System.

Es steht eine Anzahl Positionen und eine Anzahl Mitarbeiter in 2 versch. Arrays zur Verfügung.
Der Array der Mitarbeiter enthält alle Positionen, die ein Mitarbeiter einnehmen kann (in diesem Test zB auch Ersetzen des "Chefs" durch einen anderen Mitarbeiter möglich).

Nun sind alle möglichen Kombinationen (Bäume) gesucht, wie die Mitarbeiter auf die Positionen aufgeteilt werden können. Alle Positionen müssen jeweils gefüllt werden pro Baum.

Mein bisheriger Algorithmus findet nicht alle möglichen Bäume, überschreibt teilweise vorhandene Ergebnisse und ich komme bei meinen Überlegungen nicht weiter.
Anbei der Code, hat jemand eine Idee? DANKE

<?php

$positions = array (
	'Chef1' 	=> 1,
	'Chef2' 	=> 1,
	'MA1' 		=> 2,
	'MA2' 		=> 2,
	'MA3' 		=> 2,
	'MA4' 		=> 2
);

$employees = array (
	'D1' => array('Chef1'),
	'D2' => array('Chef2'),
	'D3' => array('MA1','Chef1'),
	'D4' => array('MA2','Chef2'),
	'D5' => array('MA3'),
	'D6' => array('MA4'),
	'D7' => array('MA4', 'MA3', 'Chef2'),
	'D8' => array('MA2', 'MA1', 'Chef1') 
);


//create empty tree, chain
$chain = array(); //chain is array of all found trees
$tree = array();
foreach ($positions as $pos => $val) {
	array_push($tree, array('$pos' => ""));
}

function getTree($positions, $employees, $tree, &$chain, $count, $pos = null, $employee = null) {
	$max_recursive = 5;


	//save original arrays for recursive call
	$save1 = $positions;
	$save2 = $employees;
	
	//preset for new element for chain
	if($pos != null) {
		$positionsCount = $count;
		$chain[$count][$pos] = $employee;
		unset($emplyees[$employee]);
		unset($positions[$pos]);
	}

	//für jede Positions suche
	foreach ($positions as $pos => $val1) {
		//für jeden mitarbeiter suche
		foreach ($employees as $employee => $ePositions) {
			foreach ($ePositions as $ePos) {
				
				//falls Mitarbeiter Position ausführen kann
				if ($ePos == $pos) {
					//und falls noch nicht im aktuellen $tree gespeichert
					if (!isset($chain[$count][$pos])) {
						//setze Zuordnung im $tree
						$chain[$count][$pos] = $employee;
					}
					else {
						if ($count <= $max_recursive) {
							//falls Wert bereits vorhanden, mache neuen $tree
							$next = $count + 1;
							getTree($save1, $save2, $tree, $chain, $next, $pos, $employee);
						}
					}
					//lösche "gebrauchte" felder, da ansonsten doppelbelegungen möglich
					unset($employees[$employee]);
					unset($positions[$pos]);
				}
			}
		}
	}
}

getTree($positions, $employees, $tree, $chain, 0);
printf( "\n<pre>%s</pre>\n", print_r($chain, 1) );


?>