4

我正在尝试为足球联赛生成赛程表。我已经成功地生成了实际的赛程表，没有任何问题，但现在我正在尝试生成要进行比赛的“周”。这只需要“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

对此的任何帮助将不胜感激。

4

1 回答 1

4

以下解决方案有效，但我认为对于不是 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.

使用我的“纸笔”方法，我注意到在矩阵上沿对角线排列数字非常理想，在回家的路上，我想到了一种方法，您可以只输入 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;
}
于 2012-10-30T18:13:43.420 回答