[php] Algorithmus Kombinatorik

Valmont

Grünschnabel
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:
<?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) );


?>
 
Zurück