Creating matrix of numbers unique in row and column

Question

If you can come up with a better title after reading the question, please feel free to change it.

So, as input I have an integer, which is an even number between 2 and 20. Let's call this integer $teams. What I need to do is generate a $teams x $teams sized matrix of numbers between 1 and $teams-1 (inclusive) while respecting the following rules:

The diagonal (from top left to bottom right) has value -1.
The same number may not appear in the same column or row more than once.
If a number appears in column N, then in may not appear in row N. For example, if it appears in column #2, it may not appear in row #2, etc.

Note that we're only looking at the part above the diagonal. The part below it is just a reflection of that (each number is its reflection + $teams - 1), and it doesn't matter for this problem.

The first 2 conditions were fairly easy to accomplish, but the 3rd one is killing me. I don't know how to make it happen, especially since the $teams number could be any even number between 2 and 20. The code that gives a correct output for conditions 1 and 2 is given below. Can someone help me with condition number 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;
}

The current code (for $teams=6) gives the following output:

  -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

As you see, the number 1 appears both in the 2nd column and 2nd row, number 4 appears both in the 5th column and 5th row etc, which breaks rule #3.

Maybe there are easier solutions, but you could have a look at backtracking: en.wikipedia.org/wiki/Backtracking — Misch
Thanks, but I'd rather explore easier potential solutions first. Backtracking looks like it could definitely solve it, but would take a lot of effort and doesn't seem very efficient in terms of number of iterations (though that's not too much of an issue considering the small number of $teams). — robert
One thing that occurred to me is when you said "the number appears in the n th column", that refers to the nth collumn of the first row. Well, you know that in the first row you have the numbers from -1 to n-1. When you generate the numbers for row number x you can easily skip the number which is in $games[1][x]. Hope that helps somewhat ;-) — Havelock
@Havelock I will try that, thanks. I suspect that the last row will have a wrong entry though, since there will be no choice at that point. — robert
@robert I'd say try to get a correct solution on a piece of paper first, to then see whether you can extract some dependency between the numbers in the rows and columns, that would lead you to the correct algorithm. — Havelock

Terje D. Terje D. · Accepted Answer · 2013-04-14T21:51:51

The question can be solved without any guessing or backtracing by creating a round-robin schedule for n teams playing against each other in n rounds, then from this build an array representing the schedule as described in the question

To build the schedule place the n (here 6) teams in two rows

1 2 3
6 5 4

This is round 1, where 1 meets 6, 2 meets 5, and 3 meets 4.

Then for each round, rotate the teams except team 1, giving the complete schedule

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

This can be represented as an array with each row representing one week in which the team in the first column meets the team in the last, second meets second last etc.

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)

Representing the teams as rows and columns, with weeks as table entries, this becomes

-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

Following is the code to generate this for various number of 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);

Creating matrix of numbers unique in row and column

4 Answers