How to generate a fixture list in PHP/MySQL?

mysql, php

Solution

The following solution works, but I don't think it fills the schedule as efficiently as is possible for numbers of teams that are not powers of two. Also the efficiency of the code is n^2 [possibly n^3?] for all cases, so I hope you don't need to schedule more than a few hundred teams at once. :P

<?php
$teams = $_GET['t'];
$games = array();   //2D array tracking which week teams will be playing
$weeks = array();   //2D array tracking which teams are playing in a given week

// initialize
for( $i=0; $i<$teams; $i++ ) {
    $games[$i] = array();
    for( $j=0; $j<$teams; $j++ ) {
        if( $i == $j ) { $games[$i][$j] = -1; } //you can't play with yourself ;D
        else { $games[$i][$j] = NULL; }
    }
}

// do the work
for( $w=1, $noblanks=false; !$noblanks; $w++) {
    if( !isset($weeks[$w]) ) { $weeks[$w] = array(); }
    $noblanks = true;   //begin assuming there are no blank spots in the matrix
    for( $i=0; $i<$teams; $i++ ) {
        for( $j=0; $j<$teams; $j++ ) {
            if( $i == $j ) { continue; }    //you can't play with yourself ;D
            if( is_null($games[$i][$j]) ) {
                if( !isset($weeks[$w][$i]) && !isset($weeks[$w][$j]) ) {
                    $games[$i][$j] = $w;    //game between team i and j in week w
                    $weeks[$w][$i] = true;  //mark that team i has game in week w
                    $weeks[$w][$j] = true;  //mark that team j has game in week w
                } else { $noblanks = false; } //this cell is blank, and will be left blank.
            }
        }
    }
}

// display
echo '<pre>';
foreach($games as $row) {
    foreach($row as $col) {
        printf('%4d', is_null($col) ? -2 : $col);
    }
    echo "\n";
}
printf("%d teams in %d weeks\n", $teams, count($weeks));
echo '</pre>';

Sample output:

  -1   1   2   3
   4  -1   3   2
   5   6  -1   1
   6   5   4  -1
4 teams in 6 weeks

  -1   1   2   3   4   5   6
   7  -1   3   2   5   4   8
   8   6  -1   1   7   9   4
   9  10   5  -1   6   7  11
  10   9  11   8  -1   1   2
  11  12  10  13   3  -1  14
  12  13  15  16  17  18  -1
7 teams in 18 weeks

Edit

I've figured out a method that's more 'week-efficient' for all cases except where the number of teams is a power of two. Essentially the number of weeks require becomes `2 * number_of_teams`.

With my 'pen-and-paper' methods I noticed that striping numbers diagonally across the matrix is pretty much ideal, and on my walk home I thought up a method where you can just feed in 2 team IDs, and a count of teams and it will give you back the week that that game should take place.

<?php

function getweek($home, $away, $num_teams) {
    if($home == $away) { return -1; }
    $week = $home+$away-2;
    if( $week > ($num_teams) ) {
        $week = $week-$num_teams;
    }
    if( $home>$away ) {
        $week += $num_teams;
    }
    return $week;
}

$teams = $_GET['t'];
$games = array();   //2D array tracking which week teams will be playing

// do the work
for( $i=1; $i<=$teams; $i++ ) {
    $games[$i] = array();
    for( $j=1; $j<=$teams; $j++ ) {
        $games[$i][$j] = getweek($i, $j, $teams);
    }
}

// display
echo '<pre>';
$max=0;
foreach($games as $row) {
    foreach($row as $col) {
        printf('%4d', is_null($col) ? -2 : $col);
        if( $col > $max ) { $max=$col; }
    }
    echo "\n";
}
printf("%d teams in %d weeks, %.2f weeks per team\n", $teams, $max, $max/$teams);
echo '</pre>';

Example Output:

  -1   1   2   3
   5  -1   3   4
   6   7  -1   1
   7   8   5  -1
4 teams in 8 weeks, 2.00 weeks per team

  -1   1   2   3   4   5   6
   8  -1   3   4   5   6   7
   9  10  -1   5   6   7   1
  10  11  12  -1   7   1   2
  11  12  13  14  -1   2   3
  12  13  14   8   9  -1   4
  13  14   8   9  10  11  -1
7 teams in 14 weeks, 2.00 weeks per team

Edit (Apr 2013)

I have modified the `getWeek()` function to work for any number of teams. See the new function below. Jovan

function getWeek($home, $away, $num_teams) {
    if($home == $away){
        return -1;
    }
    $week = $home+$away-2;
    if($week >= $num_teams){
        $week = $week-$num_teams+1;
    }
    if($home>$away){
        $week += $num_teams-1;
    }

    return $week;
}

Problem

Original source