Round Robin Algorithm

Generating a Schedule Automatically

I need to create a way for every team to play each other in each round of games. I first started out creating a chart of who each team will play. After I created a chart that worked I built an algorithm to build that chart.

The Game Schedule

The Teams: Team 1 Team 2 Team 3 Team 4 Team 5 Team 6
Rounds: Round 1 Team 6 Team 5 Team 4 Team 3 Team 2 Team 1
Round 2 Team 4 Team 6 Team 5 Team 1 Team 3 Team 2
Round 3 Team 2 Team 1 Team 6 Team 5 Team 4 Team 3
Round 4 Team 5 Team 3 Team 2 Team 6 Team 1 Team 4
Round 5 Team 3 Team 4 Team 1 Team 2 Team 6 Team 5

Now you just need to figure out the pattern and we can code it up. I was told there is a name for this pattern but I didn’t know it, so if you know it let me know.

The Variables

$gamearr AND $tempgamearr are both an array of all the teams. The array would look like this: $gamearr[0] = “firstteam”, $gamearr[1] = “secondteam” and so on.

$numteamspadded is the number of teams. If the number was odd I add another team to the end of $gamearr and $tempgamearr as a “byteam”.

$gamenumperteam is however many number of games you want each team to play.

The Logic

As you can see at the beginning I set the variable $firstteam. You realize why I did this if you figured out the pattern above. The pattern above being that I have an array of teams playing the array of teams in reverse order. After each round I decrement the reverse order array and move the last one to the front. So we would have 654321 and then 165432 and then 216543. This would cause teams to play themselves though which is where the $firstteam comes in. Every time a team would play itself we switch it out with the firstteam.

I start out by looping through the number of games and then looping through just half of the teams since I’m setting both the home and away team in there. If I looped through all the teams I would have 1 vs 6 and then 6 vs 1 but I just want the unique games.

I then loop through all the games and set the $gamearr to the values that it would be had I been just decrementing the array and moving the last item to the beginning. Meaning the gamearr will look like this after each round 234561, 345612, 456123, etc. I use the $tempgamearr because I need to know the original order of the teams since we have to switch the first team out when there is a game playing itself.
After this I remove the first team from the array. I then loop through the game to find if one of the teams will be playing itself and get its value and position. This is one of the reasons why I remove the first team from the array. If I left it in there then 1 would play itself and overwrite the fact that another team was playing itself.
I then switch the team that is playing itself with the $firstteam.

After this you have an array of the games for each round.
I then create an array of all the games and check to see if the “byweek” is playing. If it is I don’t add it to the array cause we don’t want a byweek taking up a game slot.

The Round Robin Algorithm


$bottom = $numteamspadded-1;
$half = $numteamspadded/2;

$firsteam = $gamearr[0];
for($i=0; $i<$gamenumperteam; $i++){
    for($j=0; $j<$half; $j++){
         if($numteamspadded==4)
           $rrarr[$i][$j]['home'] = $tempgamearr[$j];
        else $rrarr[$i][$j]['home'] = $gamearr[$j];
        $rrarr[$i][$j]['away'] = $gamearr[$bottom-$j];
    }

    for($j=1; $j<=$bottom+1; $j++){
        $start = ($i+$j)%$numteamspadded;
        $gamearr[$j-1] = $tempgamearr[$start];
    }

    array_splice($gamearr, array_search($firsteam, $gamearr), 1);
    foreach($gamearr as $key=>$val){
        if($tempgamearr[$bottom-$key] == $val){
              $TempGameValue = $val;
              $switch = $key;
          }
    }

    $gamearr[$bottom] = $TempGameValue;
    $gamearr[$switch] = $firsteam;
}
foreach($rrarr as $key=>$val){
  foreach($val as $gkey=>$games){
    if($games['home'] != 'byweek' && $games['away'] != 'byweek'){
      $allgames[] = $games;
    }
  }
}

UPDATE: I came across another good implementation of the round robin here at http://phpbuilder.com/board/showthread.php?p=10935200

Comments are closed.