Double-Elimination Tournament Schedule
double-elimination, loops, php, tournament
Solution
Well, I've been trudging through my existing logic and was able to generate the schedule for 4-, 8-, 16-, and 32-team double elimination brackets. The logic is not the must succinct, but it at least allows me to understand what's going on. In the future, I hope to revise and clean it up a bit, but for now this will have to do.
$rounds = log( count( $competitors ), 2 ) + 1;
// round one
for( $i = 0; $i < log( count( $competitors ), 2 ); $i++ )
{
$seeded = array( );
foreach( $competitors as $competitor )
{
$splice = pow( 2, $i );
$seeded = array_merge( $seeded, array_splice( $competitors, 0, $splice ) );
$seeded = array_merge( $seeded, array_splice( $competitors, -$splice ) );
}
$competitors = $seeded;
}
$events = array_chunk( $seeded, 2 );
if( $rounds > 2 )
{
$round_index = count( $events );
// second round
for( $i = 0; $i < count( $competitors ) / 2; $i++ )
{
array_push( $events, array(
array( 'from_event_index' => $i, 'from_event_rank' => 1 ), // rank 1 = winner
array( 'from_event_index' => ++$i, 'from_event_rank' => 1 )
) );
}
$round_matchups = array( );
for( $i = 0; $i < count( $competitors ) / 2; $i++ )
{
array_push( $round_matchups, array(
array( 'from_event_index' => $i, 'from_event_rank' => 2 ), // rank 2 = loser
array( 'from_event_index' => ++$i, 'from_event_rank' => 2 )
) );
}
$events = array_merge( $events, $round_matchups );
for( $i = 0; $i < count( $round_matchups ); $i++ )
{
array_push( $events, array(
array( 'from_event_index' => $i + count( $competitors ) / 2, 'from_event_rank' => 2 ),
array( 'from_event_index' => $i + count( $competitors ) / 2 + count( $competitors ) / 2 / 2, 'from_event_rank' => 1 )
) );
}
}
if( $rounds > 3 )
{
// subsequent rounds
for( $i = 0; $i < $rounds - 3; $i++ )
{
$round_events = pow( 2, $rounds - 3 - $i );
$total_events = count( $events );
for( $j = 0; $j < $round_events; $j++ )
{
array_push( $events, array(
array( 'from_event_index' => $j + $round_index, 'from_event_rank' => 1 ),
array( 'from_event_index' => ++$j + $round_index, 'from_event_rank' => 1 )
) );
}
for( $j = 0; $j < $round_events; $j++ )
{
array_push( $events, array(
array( 'from_event_index' => $j + $round_index + $round_events * 2, 'from_event_rank' => 1 ),
array( 'from_event_index' => ++$j + $round_index + $round_events * 2, 'from_event_rank' => 1 )
) );
}
for( $j = 0; $j < $round_events / 2; $j++ )
{
array_push( $events, array(
array( 'from_event_index' => $j + $total_events, 'from_event_rank' => 2 ),
array( 'from_event_index' => $j + $total_events + $round_events / 2, 'from_event_rank' => 1 )
) );
}
$round_index = $total_events;
}
}
if( $rounds > 1 )
{
// finals
array_push( $events, array(
array( 'from_event_index' => count( $events ) - 3, 'from_event_rank' => 1 ),
array( 'from_event_index' => count( $events ) - 1, 'from_event_rank' => 1 )
) );
}
I've verified the results up to 32 teams (powers of 2, only) and was able to generate a schedule with 64 teams that appears to be correct. Sometimes, persistence pays off.
Problem
I'm trying to create some logic to generate a schedule of events in a double-elimination tournament bracket. Here is an example 8-team bracket: ``` rd1 quarter semi finals A───┐ 0 ├───────A┐ B───┘ │ 4 ├────────A┐ C───┐ │ │ 1 ├───────C┘ │ D───┘ │ 10 ├──────A┐ E───┐ │ │ 2 ├───────E┐ │ │ F───┘ │ │ │ 5 ├────────E┘ │ G───┐ │ 13 ├───= Champ 3 ├───────G┘ │ H───┘ │ E────┐ │ C───┐ │ │ B───┐ 8 ├────C┐ 12 ├────E┘ 6 ├B───┘ │ │ D───┘ 11 ├C────┘ G───┐ │ F───┐ 9 ├────G┘ 7 ├F───┘ H───┘ ``` The numbers represent indices in an array of matches, which is the desired output. For example, index 0 will represent Team 1 vs. Team 8 (using a seeded system), index 4 will represent the Winner of index 0 vs. the Winner of index 1. The loser's bracket is populated from the losers of the winner's bracket, where index 6 is the Loser of index 0 vs. the Loser of index 1 and index 8 is the Loser of of index 4 vs. the Winner of index 6. In the visual example, you can see the teams labelled by letter and showing a clear example of the winning team being on the top branch every time, and the losing team being on the bottom branch. Index 0 represents Team A vs. B, index 4 represents the winner of index 0 (A) vs. the winner of index 1 (C). Index 6 is the loser of Index 0 (B) vs. the loser of Index 1 (D) and index 8 is the loser of index 4 (C) vs. the winner of index 6 (B) There is a obvious pattern emerging, but my logic gets messed up and confusing when I try to adapt for varying numbers of competitors. For simplicity's sake, I'm fixing the bracket to only a power of 2 number of teams. I was able to write everything to create an array of matches for an 8-team bracket, but I'm getting lost understanding even my own code, since it doesn't seem to be scalable. ``` // round one for( $i = 0; $i < log( count( $competitors ), 2 ); $i++ ) { $seeded = array( ); foreach( $competitors as $competitor ) { $splice = pow( 2, $i ); $seeded = array_merge( $seeded, array_splice( $competitors, 0, $splice ) ); $seeded = array_merge( $seeded, array_splice( $competitors, -$splice ) ); } $competitors = $seeded; } $events = array_chunk( $seeded, 2 ); // quarter finals for( $i = 0; $i < count( $competitors ) / 2; $i++ ) { array_push( $events, array( array( 'from_event_index' => $i, 'from_event_rank' => 1 ), // rank 1 = winner array( 'from_event_index' => ++$i, 'from_event_rank' => 1 ) ) ); } $round_matchups = array( ); for( $i = 0; $i < count( $competitors ) / 2; $i++ ) { array_push( $round_matchups, array( array( 'from_event_index' => $i, 'from_event_rank' => 2 ), // rank 2 = loser array( 'from_event_index' => ++$i, 'from_event_rank' => 2 ) ) ); } $events = array_merge( $events, $round_matchups ); for( $i = 0; $i < count( $round_matchups ); $i++ ) { array_push( $events, array( array( 'from_event_index' => $i + count( $competitors ) / 2, 'from_event_rank' => 2 ), array( 'from_event_index' => $i + count( $competitors ) / 2 + count( $competitors ) / 2 / 2, 'from_event_rank' => 1 ) ) ); } // semi finals for( $i = 0; $i < count( $competitors ) / 2 / 2; $i++ ) { array_push( $events, array( array( 'from_event_index' => $i + count( $competitors ) / 2, 'from_event_rank' => 1 ), array( 'from_event_index' => ++$i + count( $competitors ) / 2, 'from_event_rank' => 1 ) ) ); } $round_matchups = array( ); for( $i = 0; $i < count( $competitors ) / 2 / 2; $i++ ) { array_push( $round_matchups, array( array( 'from_event_index' => $i + count( $competitors ), 'from_event_rank' => 1 ), array( 'from_event_index' => ++$i + count( $competitors ), 'from_event_rank' => 1 ) ) ); } $events = array_merge( $events, $round_matchups ); for( $i = 0; $i < count( $round_matchups ); $i++ ) { array_push( $events, array( array( 'from_event_index' => $i + count( $competitors ) + count( $competitors ) / 2 - 2, 'from_event_rank' => 2 ), array( 'from_event_index' => $i + count( $competitors ) + count( $competitors ) / 2 - 1, 'from_event_rank' => 1 ) ) ); } // finals for( $i = 0; $i < count( $competitors ) / 2 / 2 / 2; $i++ ) { array_push( $events, array( array( 'from_event_index' => $i + count( $competitors ) / 2 * 3 - 2, 'from_event_rank' => 1 ), array( 'from_event_index' => ++$i + count( $competitors ) / 2 * 3 - 1, 'from_event_rank' => 1 ) ) ); } ``` Output of the code above: ``` $events = array(14) { [0]=> array(2) { [0]=> array(4) { ["team"]=>int(1) } [1]=> array(4) { ["team"]=>int(8) } } [1]=> array(2) { [0]=> array(4) { ["team"]=>int(4) } [1]=> array(4) { ["team"]=>int(5) } } [2]=> array(2) { [0]=> array(4) { ["team"]=>int(2) } [1]=> array(4) { ["team"]=>int(7) } } [3]=> array(2) { [0]=> array(4) { ["team"]=>int(3) } [1]=> array(4) { ["team"]=>int(6) } } [4]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(0) ["from_event_rank"]=>int(1) } [1]=> array(2) { ["from_event_index"]=>int(1) ["from_event_rank"]=>int(1) } } [5]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(2) ["from_event_rank"]=>int(1) } [1]=> array(2) { ["from_event_index"]=>int(3) ["from_event_rank"]=>int(1) } } [6]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(0) ["from_event_rank"]=>int(2) } [1]=> array(2) { ["from_event_index"]=>int(1) ["from_event_rank"]=>int(2) } } [7]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(2) ["from_event_rank"]=>int(2) } [1]=> array(2) { ["from_event_index"]=>int(3) ["from_event_rank"]=>int(2) } } [8]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(4) ["from_event_rank"]=>int(2) } [1]=> array(2) { ["from_event_index"]=>int(6) ["from_event_rank"]=>int(1) } } [9]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(5) ["from_event_rank"]=>int(2) } [1]=> array(2) { ["from_event_index"]=>int(7) ["from_event_rank"]=>int(1) } } [10]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(4) ["from_event_rank"]=>int(1) } [1]=> array(2) { ["from_event_index"]=>int(5) ["from_event_rank"]=>int(1) } } [11]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(8) ["from_event_rank"]=>int(1) } [1]=> array(2) { ["from_event_index"]=>int(9) ["from_event_rank"]=>int(1) } } [12]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(10) ["from_event_rank"]=>int(2) } [1]=> array(2) { ["from_event_index"]=>int(11) ["from_event_rank"]=>int(1) } } [13]=> array(2) { [0]=> array(2) { ["from_event_index"]=>int(10) ["from_event_rank"]=>int(1) } [1]=> array(2) { ["from_event_index"]=>int(12) ["from_event_rank"]=>int(1) } } } ``` Any ideas on how I can modify this to work for a 4-team, 16-team, or 2^n-team bracket? I feel like the logic under the heading "semi-finals" is what should repeat 0+ times, but every time I try to loop it based on the total number of rounds, it just repeats the same matches as the previous round.