php - 如何在 PHP/MySQL 中生成夹具列表？

Question

我正在尝试为足球联赛生成赛程表。我已经成功地生成了实际的赛程表，没有任何问题，但现在我正在尝试生成要玩游戏的“周”。这只需要是“1 到 n”，没有其他日期信息，只有一周数。

我在MySQL中创建的表如下:

Home     Away GameID WeekID
Team 2  Team 1  1      0
Team 3  Team 1  2      0
Team 3  Team 2  3      0
Team 4  Team 1  4      0
Team 4  Team 2  5      0  
Team 4  Team 3  6      0
Team 1  Team 2  7      0
Team 1  Team 3  8      0
Team 2  Team 3  9      0
Team 1  Team 4  10     0
Team 2  Team 4  11     0
Team 3  Team 4  12     0

每支球队都必须打主客场比赛，因此有些比赛会重复进行。然而，我需要做的是，如前所述，为比赛分配一个周数，一个团队每周只能比赛一次。

我要创建的是:

Home     Away GameID WeekID
Team 2  Team 1  1      1
Team 3  Team 1  2      2
Team 3  Team 2  3      3
Team 4  Team 1  4      4
Team 4  Team 2  5      5 
Team 4  Team 3  6      6
Team 1  Team 2  7      6
Team 1  Team 3  8      5
Team 2  Team 3  9      4
Team 1  Team 4  10     3
Team 2  Team 4  11     2
Team 3  Team 4  12     1

如有任何帮助，我们将不胜感激。

Answer 1

以下解决方案有效，但我认为对于数量不是 2 的幂的团队而言，它无法尽可能高效地填满日程表。此外，对于所有情况，代码的效率都是 n^2 [可能是 n^3？]，所以我希望您不需要一次安排超过几百个团队。 :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>';

示例输出:

  -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

编辑

我找到了一种对所有情况都更“周高效”的方法，除了团队数量是 2 的幂的情况。本质上，所需的周数变为 2 * number_of_teams。

用我的' pen-and-paper ' 方法 我注意到在矩阵中沿对角线排列数字非常理想，在回家的路上我想到了一种方法，您可以只输入 2 个团队 ID 和一些团队，它会返回一周那场比赛应该举行。

<?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>';

示例输出:

  -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

编辑(2013 年 4 月)

我修改了 getWeek() 函数以适用于任意数量的团队。请参阅下面的新功能。乔万

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;
}