Erstellung matrix von zahlen, die einzigartig in Zeile und Spalte

Kann die Frage gelöst werden, ohne das schätzen oder die backtracing durch die Schaffung eines round-robin-Zeitplan für die n-teams spielen gegen einander in n Runden, dann von diesem build ein array mit den Zeitplan wie beschrieben in der Frage

Bauen Sie den Zeitplan Ort der n (hier 6) teams, die in zwei Reihen

1 2 3
6 5 4

Dies ist Runde 1, wo 1 erfüllt 6, 2 erfüllt, 5, und 3 erfüllt 4.

Dann für jede Runde, drehen die teams, außer team 1, was den kompletten Zeitplan

Round 1    Round 2    Round 3    Round 4    Round 5
1 2 3      1 3 4      1 4 5      1 5 6      1 6 2    
6 5 4      2 6 5      3 2 6      4 3 2      5 4 3  

Diese können dargestellt werden als ein array mit jeder Zeile, die eine Woche, in der das team in der ersten Spalte trifft sich das team in der letzten Sekunde erfüllt die vorletzte usw.

1 2 3 4 5 6  (Week 1: 1-6, 2-5, 3-4)
1 3 4 5 6 2  (Week 2: 1-2, 3-6, 4-5)
1 4 5 6 2 3  (Week 3: 1-3, 2-4, 5-6)
1 5 6 2 3 4  (Week 4: 1-4, 3-5, 2-6)
1 6 2 3 4 5  (Week 5: 1-5, 4-6, 2-3)

Vertreter der teams, die als Zeilen und Spalten, mit Wochen, wie die Einträge der Tabelle, diese wird

-1  1  2  3  4  5
 6 -1  4  2  5  3
 7  9 -1  5  3  1
 8  7 10 -1  1  4
 9 10  8  6 -1  2
10  8  6  9  7 -1 

Folgende code ist der code zu generieren, diese für verschiedene Anzahl teams:

<?php

function buildSchedule($teams) {
  //Returns a table with one row for each round of the tournament                   
  //Matrix is built by rotating all entries except first one from row to row,       
  //giving a matrix with zeroes in first column, other values along diagonals       
  //In each round, team in first column meets team in last,                         
  //team in second column meets second last etc.                                    
  $schedule = array();
  for($i=1; $i<$teams; $i++){
    for($j=0; $j<$teams; $j++){
      $schedule[$i][$j] = $j==0 ? 0 : ($i+$j-1) % ($teams-1) + 1;
    }
  }
  return $schedule;
}

function buildWeekTable($schedule) {
  //Convert schedule into desired format                                            

  //create n x n array of -1                                                         
  $teams = sizeof($schedule)+1;
  $table = array_pad(array(), $teams, array_pad(array(), $teams, -1));

  //Set table[i][j] to week where team i will meet team j                           
  foreach($schedule as $week => $player){
    for($i = 0; $i < $teams/2 ; $i++){
      $team1 = $player[$i];
      $team2 = $player[$teams-$i-1];
      $table[$team1][$team2] = $team2 > $team1 ? $week : $week + $teams -1;
      $table[$team2][$team1] = $team1 > $team2 ? $week : $week + $teams -1;
    }
  }
  return $table;
}

function dumpTable($table){
  foreach($table as $row){
    $cols = sizeof($row);
    for($j=0; $j<$cols; $j++){
      printf(" %3d", isset($row[$j]) ? $row[$j] : -1);
    }
    echo "\n";
  }
}

$teams = 6;

$schedule = buildSchedule($teams);
$weekplan = buildWeekTable($schedule);
dumpTable($weekplan);

AKTUALISIERT: ich habe versucht, zu implementieren eine Lösung mit backtracking. Der code könnte wahrscheinlich ein umschreiben (vielleicht eine Klasse) und Dinge, die optimiert werden konnten.

Die Idee ist ein Spaziergang durch alle Lösungen, aber halt eine Filiale, sobald klar wird, dass der Zweig bricht eine der drei Regeln. Mit 6 teams, eine Lösung gefunden werden, in 71 versucht - auch wenn es theoretisch besteht 759,375 Kombinationen.

Sehen http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF für die Berechnung der Gesamt-Spiele benötigt.

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

Er druckt:

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