17

質問を読んでもっといいタイトルが思いついたら、自由に変更してください。

したがって、入力として整数があり、これは 2 から 20 までの偶数です。この整数を と呼びましょう$teams。私がする必要があるのは、次のルールを尊重しながら$teams x $teams、1 から (1 を含む) までのサイズの数値の行列を生成することです。$teams-1

  1. 対角線 (左上から右下へ) の値は -1 です。
  2. 同じ列または行に同じ数字が複数回出現することはありません。
  3. 数値が列 N に表示される場合、行 N には表示されない場合があります。たとえば、列 #2 に表示される場合、行 #2 には表示されない可能性があります。

対角線より上の部分だけを見ていることに注意してください。その下の部分はそれを反映したものに過ぎず (各数字はその反映 + $teams - 1)、この問題には関係ありません。

最初の 2 つの条件はかなり簡単に達成できましたが、3 番目の条件は私を殺しています。特に、数値は 2 から 20 の間の任意の偶数である可能性があるため、それを実現する方法がわかりません$teams。条件 1 と 2 の正しい出力を与えるコードを以下に示します。誰かが条件番号3で私を助けることができますか?

$teams = 6;         //example value - should work for any even Int between 2 and 20
$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);
    }
}

//show output
echo '<pre>';
$max=0;
foreach($games as $key => $row) {
    foreach($row as $k => $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>';

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

現在のコード ($teams=6 の場合) では、次の出力が得られます。

  -1   1   2   3   4   5
   6  -1   3   4   5   1
   7   8  -1   5   1   2
   8   9  10  -1   2   3
   9  10   6   7  -1   4
  10   6   7   8   9  -1
6 teams in 10 weeks, 1.67 weeks per team

ご覧のとおり、数値 1 は 2 列目と 2 行目の両方に表示され、数値 4 は 5 列目と 5 行目の両方に表示されます。これはルール #3 に違反しています。

4

4 に答える 4

0

getWeek()1 つの解決策は、除外したい数値を含む配列 (つまり、現在の行に相当する列にあるすべての数値を含む配列) に渡すことです。

このような除外配列を作成して、次のgetWeek()ように渡すことができます。

//do the work
for( $i=1; $i<=$teams; $i++ ) {
    $games[$i] = array();
    for( $j=1; $j<=$teams; $j++ ) {
        $exclude = array();
        for ( $h=1; $h<=$i; $h++ ) {
           if ( isset($games[$h][$j]) ) {
              $exclude[] = $games[$h][$j];
           }
        }
        $games[$i][$j] = getWeek($i, $j, $teams, $exclude);
    }
}

次に、次のように、配列にgetWeek()渡された数値のいずれかが含まれないようにチェックインする必要があります。$exclude

function getWeek($home, $away, $num_teams, $exclude) {
    //
    // Here goes your code to calculate $week
    //

    if (in_array($week, $exclude)) {
       //the calculated $week is in the $exclude array, so you need
       //to calculate a new value which is not in the $exclude array
       $week = $your_new_valid_value;
    }

    return $week;
}
于 2013-04-14T14:42:47.177 に答える
-1

更新: バックトラッキングを使用して解決策を実装しようとしました。コードはおそらく書き直しが必要になる可能性があり（おそらくクラス）、物事が最適化される可能性があります。

アイデアは、すべてのソリューションをウォークスルーすることですが、ブランチが 3 つのルールのいずれかに違反していることが明らかになり次第、ブランチを停止します。6 チームの場合、理論的には 759,375 通りの組み合わせがありますが、71 回の試行で解が見つかります。

必要な合計ゲーム数の計算については、 http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AFを参照してください。

<?php
$size = 10;

$gamesPerTeam = $size-1;
$games = ($gamesPerTeam*($gamesPerTeam+1))/2;

$gamePlan = array_fill(0, $games, 1);

function increaseGamePlan(&$gamePlan, $pointOfFailure, $gamesPerTeam) {
    if ($gamePlan[$pointOfFailure] === $gamesPerTeam) {
        $gamePlan[$pointOfFailure] = 1;
        increaseGamePlan($gamePlan, $pointOfFailure-1, $gamesPerTeam);
    } else {
        $gamePlan[$pointOfFailure]++;
    }

}

function checkWeekFor($i, $row, $column, &$pools) {
    if ($column-$row <= 0)
        return '-';

    if (!in_array($i, $pools['r'][$row]) && !in_array($i, $pools['c'][$column]) && !in_array($i, $pools['c'][$row])) {
        $pools['r'][$row][] = $i;
        $pools['c'][$column][] = $i;
        return true;
    }
}

$a = 0;
while (true) {
    $a++;
    $m = [];

    $pools = [
        'r' => [],
        'c' => [],
    ];
    $i = 0;
    for ($row = 0;$row < $size;$row++) {
        $m[$row] = array();
        $pools['r'][$row] = array();
        for ($column = 0;$column < $size;$column++) {
            if ($column-$row <= 0)
                continue;

            if (!isset($pools['c'][$column]))
                $pools['c'][$column] = array();

            if (!isset($pools['c'][$row]))
                $pools['c'][$row] = array();

            $week = $gamePlan[$i];
            if (!checkWeekFor($week, $row, $column, $pools)) {
                for ($u = $i+1;$u < $games;$u++)
                    $gamePlan[$u] = 1;
                increaseGamePlan($gamePlan, $i, $gamesPerTeam);
                continue 3;
            }
            $m[$row][$column] = $week;
            $i++;
        }
    }
    echo 'found after '.$a.' tries.';
    break;
}

?>
<style>
    td {
        width: 40px;
        height: 40px;
    }
</style>
<table cellpadding="0" cellspacing="0">
    <?
    for ($row = 0;$row < $size;$row++) {
        ?>
        <tr>
            <?
            for ($column = 0;$column < $size;$column++) {
                ?>
                <td><?=$column-$row <= 0?'-':$m[$row][$column]?></td>
                <?
            }
            ?>
        </tr>
        <?
    }
    ?>
</table>

それは印刷します：

found after 1133 tries.
-   1   2   3   4   5   6   7   8   9
-   -   3   2   5   4   7   6   9   8
-   -   -   1   6   7   8   9   4   5
-   -   -   -   7   8   9   4   5   6
-   -   -   -   -   9   1   8   2   3
-   -   -   -   -   -   2   3   6   1
-   -   -   -   -   -   -   5   3   4
-   -   -   -   -   -   -   -   1   2
-   -   -   -   -   -   -   -   -   7
-   -   -   -   -   -   -   -   -   -
于 2013-04-14T15:46:09.387 に答える