Creating a game schedule with PHP _ Harder than I thought

Question

I have an array of an unknown length which will always have an evenly divisible amount of values, for example:

print_r($initialarray);

Array ( [0] => 30 [1] => 31 [2] => 32 [3] => 33 [4] => 34 [5] => 35 ) 

I need to create sets:

Set 1: 30 v 35; 31 v 34; 32 v 33;

Set 2: 30 v 34; 31 v 33; 32 v 35;

Set 3: 30 v 33; 31 v 32; 34 v 35;

Set 4: 30 v 32; 33 v 34; 31 v 35;

Set 5: 30 v 31; 32 v 34; 33 v 35; 

The order of the values are divide by v to indicate they are a set. The ordering of the values in the set does not matter (I put that together at random out of my head). As you can see there can not be duplicate sets matching in any other set or within the same set.

I have tried many different things to come up with something that works. The closest I've gotten was putting the initial values into a cascading array containing all possible valid matchups:

Array ( [0] => Array ( [0] => 35 [1] => 31 ) [1] => Array ( [0] => 34 [1] => 31 ) [2] => Array ( [0] => 33 [1] => 31 ) [3] => Array ( [0] => 32 [1] => 31 ) )

Array ( [0] => Array ( [0] => 35 [1] => 32 ) [1] => Array ( [0] => 34 [1] => 32 ) [2] => Array ( [0] => 33 [1] => 32 ) )

Array ( [0] => Array ( [0] => 35 [1] => 33 ) [1] => Array ( [0] => 34 [1] => 33 ) )

Array ( [0] => Array ( [0] => 35 [1] => 34 ) ) 

These values are arrays within one array called $sched. I left 30 out of the array.. oops

The numbers are teams. Each team needs to play each team once. The schedule will be set so that each team only plays one game each week. The schedule needs to be set over several weeks to allow all the games to be played without a team playing more than once in a week.

I have already used a permutations function and that is how I came up with array above which doesn't have identical match ups. I need to now figure out how to output the schedule as shown in the Sets above. (keeping in mind that the order the example is in doesn't matter as long as no team plays twice in the same set)

$count = count($initialarray);
$recount = $count -1;
for($u=0; $u < $count;$u++){
    for($d=0;$d<$recount;$d++){
         $vs[$u][$d] = $sched[$d][$u];
    }
$recount -= 1;
}

So that didn't work, I am complicating this beyond what it should be and I can't wrap my head around the issue anymore. Any help at all, even it means starting over, will be greatly appreciated!

Answer 1

I don't have a straight answer, but it looks like you might need a little bit of graph theory. http://en.wikipedia.org/wiki/Tournament_%28graph_theory%29

Answer 2

Maybe this code solve your problem, it is not as elegant as it could be but it seems to work. You should know ho arrangeGames works ;)

Maybe you need to pay attention on arrangePlayerforDays. It put the various games in a day only if both of the players don't have a game already scheduled on that day. The other function are just for make the code more readable (and cover a pair of glitches in arrangePlayerforDays)

function gamePrettyPrint($gamesOnADay, $glue) {
  $result=array();
  foreach ($gamesOnADay as $currentGame) 
      $result[]=join($glue,$currentGame);
  return $result;
}

function arrangeGamesOnAday($day) {
  $result=array();
  for ($k=0, $limit=count($day); $k<$limit; $k+=2)
      $result[]=array($day[$k+1], $day[$k]);
  return $result;
}

function arrangeGames($players) { 
  for ($i=0, $limit=count($players); $i < $limit; $i++) 
    for ($j=$i+1; $j<$limit;$j++) 
      $games[]=array($players[$i], $players[$j]);
  return $games;
}

function calculateTournamentDuration($players) {
  return  count($players)-1; // (n!)/(2!*(n-2)!) * (1/n)
}

function arrangePlayerforDays($games, $days) {
  $mem = array_pad(array(),$tournamentDays,array());
  for ($k=0;count($games);$k++)
    if ((array_search($games[0][0],$mem[$k%$days])=== false)  and
        (array_search($games[0][1],$mem[$k%$days])=== false))
      list($mem[$k%$days][], $mem[$k%$days][]) = array_shift($games);
  return ($mem);
}

function scatterGamesOnCalendar($games, $tournamentDays) {
  $days=arrangePlayerforDays($games, $tournamentDays);
  $calendar=array_map('arrangeGamesOnAday',$days);
  return $calendar;
}

//  $initialArray = array('a','b','c','d','e','f','g','h');
$initialArray = array(30,31,32,33,34,35);

$games= arrangeGames($initialArray);
$tournamentSpan = calculateTournamentDuration($initialArray);
$calendar = scatterGamesOnCalendar($games, $tournamentSpan);

while ($day=array_shift($calendar))
  $prettyCalendar[]=gamePrettyPrint($day,' v ');

print_r($prettyCalendar);

Answer 3

You could build a array with each "game" in it so it is sth like

0 => 30 v 35
1 => 31 v 34
2 => 32 v 33

That should be quite easy. Then you just go through this array and put the game in the first row where none of the teams is already playing. There might be better and faster solutions but this is the first that came to my mind and i think its quite simple to write.

Answer 4

Does this question have the answer you want?

Answer 5

$team = array( 1 => 30 , 2 => 31 , 3 => 32 , 4 => 33 , 5 => 34 , 6 => 35 );

$numplayers = count($team);
if ($numplayers % 2 != 0) $numplayers++; 
for ($round = 0;$round < $numplayers - 1;$round++) {
    echo 'Set ' . ($round+1) . ":\n\n{$team[1]}-";
    for ($i = 0;$i < $numplayers-1;$i++) {
        if ($i % 2 == 0) {
            $player = ($numplayers-2) - ($i/2) - $round;
        } else {
            $player = ((($i-1)/2) - $round);
        }
        if ($player < 0) $player += $numplayers - 1;
        echo $team[$player+2];
        echo ($i % 2 == 0) ? "\n" : '-';
    }
    echo "\n\n<br/>";
}