4

フットボール リーグのフィクスチャ リストを生成しようとしています。問題なく実際のフィクスチャ リストを生成することができましたが、現在、ゲームがプレイされる「週」を生成しようとしています。これは「1 から n」である必要があり、他の日付情報はなく、1 週間だけです。番号。

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

各チームはホーム アンド アウェイでプレーする必要があるため、一部のゲームでは重複が発生します。ただし、前述のように、ゲームに週番号を割り当てる必要があり、チームは週に 1 回しかプレイできません。

私が作成しようとしているのは次のとおりです。

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 のべき乗である場合を除いて、すべてのケースでより「1 週間効率的」な方法を見つけました。基本的に必要な週数は になり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 に答える