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