调度团队算法之间的匹配

Question

I am facing a scheduling problem,

We have 9 teams..We need to schedule for every team one match with every other team..

So we have 4 matches every week for 9 weeks..

Now using below function we are able to get all matches as combination 9c2

$matches = getCombinations(array(1, 2, 3, 4, 5, 6, 7, 8, 9), 2);

function getCombinations($teams, $group_length) {
    $teams_len = count($teams);
    if($group_length == 1) {
        $return = array();
        foreach($teams as $b){
            $return[] = array($b);
        }
        return $return;
    } else {
        //get one level lower combinations
        $oneLevelLower = getCombinations($teams, $group_length-1);

        //for every one level lower combinations add one element to them that the last element of a combination is preceeded by the element which follows it in base array if there is none, does not add
        $newCombs = array();

        foreach($oneLevelLower as $oll){

            $lastEl = $oll[$group_length-2];
            $found = false;
            foreach($teams as  $key => $b){
                if($b == $lastEl){
                    $found = true;
                    continue;
                    //last element found
                }
                if($found == true){
                    //add to combinations with last element
                    if($key < $teams_len){

                        $tmp = $oll;
                        $newCombination = array_slice($tmp,0);
                        $newCombination[]=$b;
                        $newCombs[] = array_slice($newCombination,0);
                    }
                }
            }
        }
    }
    return $newCombs;
}

which returns all matches..

array (size=36)
  0 => 
    array (size=2)
      0 => int 1
      1 => int 2
  1 => 
    array (size=2)
      0 => int 1
      1 => int 3
  2 => 
    array (size=2)
      0 => int 1
      1 => int 4
  3 => 
    array (size=2)
      0 => int 1
      1 => int 5
  4 => 
    array (size=2)
      0 => int 1
      1 => int 6
  5 => 
    array (size=2)
      0 => int 1
      1 => int 7
  6 => 
    array (size=2)
      0 => int 1
      1 => int 8
  7 => 
    array (size=2)
      0 => int 1
      1 => int 9
  8 => 
    array (size=2)
      0 => int 2
      1 => int 3
  9 => 
    array (size=2)
      0 => int 2
      1 => int 4
  10 => 
    array (size=2)
      0 => int 2
      1 => int 5
  11 => 
    array (size=2)
      0 => int 2
      1 => int 6
  12 => 
    array (size=2)
      0 => int 2
      1 => int 7
  13 => 
    array (size=2)
      0 => int 2
      1 => int 8
  14 => 
    array (size=2)
      0 => int 2
      1 => int 9
  15 => 
    array (size=2)
      0 => int 3
      1 => int 4
  16 => 
    array (size=2)
      0 => int 3
      1 => int 5
  17 => 
    array (size=2)
      0 => int 3
      1 => int 6
  18 => 
    array (size=2)
      0 => int 3
      1 => int 7
  19 => 
    array (size=2)
      0 => int 3
      1 => int 8
  20 => 
    array (size=2)
      0 => int 3
      1 => int 9
  21 => 
    array (size=2)
      0 => int 4
      1 => int 5
  22 => 
    array (size=2)
      0 => int 4
      1 => int 6
  23 => 
    array (size=2)
      0 => int 4
      1 => int 7
  24 => 
    array (size=2)
      0 => int 4
      1 => int 8
  25 => 
    array (size=2)
      0 => int 4
      1 => int 9
  26 => 
    array (size=2)
      0 => int 5
      1 => int 6
  27 => 
    array (size=2)
      0 => int 5
      1 => int 7
  28 => 
    array (size=2)
      0 => int 5
      1 => int 8
  29 => 
    array (size=2)
      0 => int 5
      1 => int 9
  30 => 
    array (size=2)
      0 => int 6
      1 => int 7
  31 => 
    array (size=2)
      0 => int 6
      1 => int 8
  32 => 
    array (size=2)
      0 => int 6
      1 => int 9
  33 => 
    array (size=2)
      0 => int 7
      1 => int 8
  34 => 
    array (size=2)
      0 => int 7
      1 => int 9
  35 => 
    array (size=2)
      0 => int 8
      1 => int 9

But one team can't have two matches on a day, and for every team four games are required..

So we have to arrange these matches into week schedules such that each week 8 teams play 4 matches, and one team is left..and for every team four games are there..

*PS I did not implement the combination function, its copied from someone..thnx to him..and we use php though I don't think langage matters here..

Answer 1

You can use a round-robin tournament scheduling algorithm to solve this, with nine regular teams and one "bye" team. Here is a PHP implementation.