Double-Elimination Tournament Schedule

Question

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.

Answer 1

I didn't spend much time to test this but I think it could add a lot to this topic, and share a good open code It's a tournament generator php classes with presets or custom tournaments options https://github.com/Heroyt/tournament-generator

Answer 2

This algorithm in the accepted answer is pretty complicated and hard to follow. I tried hard to but it just doesn't feel like something a developer would understand and more like a data scientist's solution. Anyways here is my solution in Kotlin:

actual fun generateDE(teams: List<Team>, bracketSize: BracketSize): Bracket {
    val matchesWQueue: Queue<Match> = ArrayDeque<Match>()
    val matchesLQueue: Queue<Match> = ArrayDeque<Match>()
    val backfillQ: Queue<Match> = ArrayDeque<Match>()
    val participants = teams.toMutableList()
    val bracket = Bracket()

    for (i in 1..bracketSize.value / 2) { // Seed Round
        var team1: Team? = null
        var team2: Team? = null

        if (participants.isNotEmpty()) {
            team1 = participants[(0..participants.size - 1).random()]
            participants.remove(team1)
        }
        if (participants.isNotEmpty()) {
            team2 = participants[(0..participants.size - 1).random()]
            participants.remove(team2)
        }

        val seedMatch = Match(
            id = UUID.randomUUID().toString(),
            team1 = team1,
            team2 = team2,
            winner = null,
            match1 = null,
            match2 = null
        )

        matchesWQueue += seedMatch
        matchesLQueue += seedMatch
        bracket.upper += seedMatch
    }

    while (matchesWQueue.size > 1) { // Generate upper bracket matches
        val match1 = matchesWQueue.remove()
        val match2 = matchesWQueue.remove()

        val matchW = Match(
            id = UUID.randomUUID().toString(),
            team1 = null,
            team2 = null,
            winner = null,
            match1 = match1,
            match2 = match2
        )

        matchesWQueue += matchW
        bracket.upper += matchW
        backfillQ += matchW // add match to backfill for Lower Queue
    }

    var roundSwitch = bracketSize.value / 2
    var switch = false
    var counter = 0
    var switchedCounter = 0
    while (matchesLQueue.size > 0 && backfillQ.size > 0) { // Generate losers bracket matches
        var match1: Match?
        var match2: Match?
        if (switch) {
            match1 = matchesLQueue.remove()
            match2 = backfillQ.remove()
            switchedCounter += 2
            if (switchedCounter == roundSwitch) {
                // switch back
                roundSwitch /= 2
                switch = false
                // reset counters
                switchedCounter = 0
            }
        } else {
            match1 = matchesLQueue.remove()
            match2 = matchesLQueue.remove()
            counter += 2
            if (counter == roundSwitch) {
                switch = true
                counter = 0
            }
        }

        val matchL = Match(
            id = UUID.randomUUID().toString(),
            team1 = null,
            team2 = null,
            winner = null,
            match1 = match1,
            match2 = match2
        )
        matchesLQueue += matchL
        bracket.lower += matchL
    }

    // Add final match
    bracket.lower += Match(
        id = UUID.randomUUID().toString(),
        team1 = null,
        team2 = null,
        winner = null,
        match1 = matchesWQueue.remove(),
        match2 = matchesLQueue.remove()
    )

    return bracket
}

Also decided to have fun with this and turn it into a Kotlin multiplatform library: https://github.com/hshar7/kotlin-brackets-multiplatform/blob/master/src/jvmMain/kotlin/brackets/BracketsJvm.kt

Answer 3

thanks for sharing this solution with us. i translated your algorithm to C#. maybe someone could use it:

using System;
using System.Collections.Generic;
using System.Linq;
using TmBackend.Entities;

namespace TmBackend.Services
{
    partial class TournamentRepository
    {
        private void GenerateDoubleEliminationMatches(Tournament tournament)
        {
            var roundsCount = Convert.ToInt32(Math.Log(tournament.Teams.Count, 2)) + 1;

            var rand = new Random();
            var shuffledTeams = tournament.Teams.OrderBy(t => rand.Next()).ToArray();

            // Round 0
            var rounds = new List<TournamentRound>
            {
                new TournamentRound
                {
                    Matches = new List<TournamentMatch>(),
                    Order = 1.0,
                    Type = TournamentRoundType.Winnerbracket,
                }
            };

            for (var i = 0; i < shuffledTeams.Length; i += 2)
            {
                rounds[0].Matches.Add(new TournamentMatch
                {
                    MatchIndex = rounds[0].Matches.Count,
                    Scores = new List<TournamentMatchScore>
                    {
                        new TournamentMatchScore
                        {
                            TournamentTeamId = shuffledTeams[i].Id
                        },
                        new TournamentMatchScore
                        {
                            TournamentTeamId = shuffledTeams[i + 1].Id
                        },
                    },
                });
            }

            var matchIndex = rounds[0].Matches.Count();
            if (roundsCount > 2)
            {
                // second round
                var winnerRound = new TournamentRound
                {
                    Matches = new List<TournamentMatch>(),
                    Order = 2,
                    Type = TournamentRoundType.Winnerbracket
                };
                rounds.Add(winnerRound);
                var loserRound = new TournamentRound
                {
                    Matches = new List<TournamentMatch>(),
                    Order = 2,
                    Type = TournamentRoundType.Loserbracket
                };
                rounds.Add(loserRound);
                var loserRound2 = new TournamentRound
                {
                    Matches = new List<TournamentMatch>(),
                    Order = 2.5,
                    Type = TournamentRoundType.Loserbracket
                };
                rounds.Add(loserRound2);

                // winner bracket
                for (var i = 0; i < shuffledTeams.Length / 2; i++)
                {
                    var m = new TournamentMatch
                    {
                        MatchIndex = matchIndex++,
                        Scores = new List<TournamentMatchScore>
                        {
                            new TournamentMatchScore
                            {
                                PreviousMatchIndex = i,
                                PreviousMatchRank = MatchRank.Winner
                            },
                            new TournamentMatchScore
                            {
                                PreviousMatchIndex = ++i,
                                PreviousMatchRank = MatchRank.Winner
                            },
                        }
                    };
                    winnerRound.Matches.Add(m);
                }

                // loser bracket 2.0
                for (var i = 0; i < shuffledTeams.Length / 2; i++)
                {
                    var m = new TournamentMatch
                    {
                        MatchIndex = matchIndex++,
                        Scores = new List<TournamentMatchScore>
                        {
                            new TournamentMatchScore
                            {
                                PreviousMatchIndex = i,
                                PreviousMatchRank = MatchRank.Loser
                            },
                            new TournamentMatchScore
                            {
                                PreviousMatchIndex = ++i,
                                PreviousMatchRank = MatchRank.Loser
                            }
                        }
                    };
                    loserRound.Matches.Add(m);
                }

                // loser bracket 2.5
                var loserRoundCount = loserRound.Matches.Count;
                for (var i = 0; i < loserRoundCount; i++)
                {
                    var m = new TournamentMatch
                    {
                        MatchIndex = matchIndex++,
                        Scores = new List<TournamentMatchScore>
                        {
                            new TournamentMatchScore
                            {
                                PreviousMatchIndex = i + shuffledTeams.Length / 2,
                                PreviousMatchRank = MatchRank.Loser
                            },
                            new TournamentMatchScore
                            {
                                PreviousMatchIndex = i + shuffledTeams.Length / 2 + shuffledTeams.Length / 2 / 2,
                                PreviousMatchRank = MatchRank.Winner
                            }
                        }
                    };
                    loserRound2.Matches.Add(m);
                }
            }


            if (roundsCount > 3)
            {
                // subsequent rounds
                for (var i = 0; i < roundsCount - 3; i++)
                {
                    var matchesCountRound = (int) Math.Pow(2, roundsCount - 3 - i);
                    var matchesCountTotalBefore = rounds.Take(rounds.Count - 3).Sum(r => r.Matches.Count);
                    var matchesCountTotal = rounds.Sum(r => r.Matches.Count);

                    var winnerRound = new TournamentRound
                    {
                        Matches = new List<TournamentMatch>(),
                        Order = 3 + i,
                        Type = TournamentRoundType.Winnerbracket
                    };
                    rounds.Add(winnerRound);
                    var loserRound = new TournamentRound
                    {
                        Matches = new List<TournamentMatch>(),
                        Order = 3 + i,
                        Type = TournamentRoundType.Loserbracket
                    };
                    rounds.Add(loserRound);
                    var loserRound2 = new TournamentRound
                    {
                        Matches = new List<TournamentMatch>(),
                        Order = 3.5 + i,
                        Type = TournamentRoundType.Loserbracket
                    };
                    rounds.Add(loserRound2);

                    // winner bracket
                    for (var j = 0; j < matchesCountRound; j++)
                    {
                        var m = new TournamentMatch
                        {
                            MatchIndex = matchIndex++,
                            Scores = new List<TournamentMatchScore>
                            {
                                new TournamentMatchScore
                                {
                                    PreviousMatchIndex = j + matchesCountTotalBefore,
                                    PreviousMatchRank = MatchRank.Winner
                                },
                                new TournamentMatchScore
                                {
                                    PreviousMatchIndex = ++j + matchesCountTotalBefore,
                                    PreviousMatchRank = MatchRank.Winner
                                },
                            }
                        };
                        winnerRound.Matches.Add(m);
                    }

                    // loser bracket X.0
                    for (var j = 0; j < matchesCountRound; j++)
                    {
                        var m = new TournamentMatch
                        {
                            MatchIndex = matchIndex++,
                            Scores = new List<TournamentMatchScore>
                            {
                                new TournamentMatchScore
                                {
                                    PreviousMatchIndex = j + matchesCountTotalBefore + matchesCountRound * 2,
                                    PreviousMatchRank = MatchRank.Winner
                                },
                                new TournamentMatchScore
                                {
                                    PreviousMatchIndex = ++j + matchesCountTotalBefore + matchesCountRound * 2,
                                    PreviousMatchRank = MatchRank.Winner
                                },
                            }
                        };
                        loserRound.Matches.Add(m);
                    }

                    // loser bracket X.5
                    for (var j = 0; j < matchesCountRound / 2; j++)
                    {
                        var m = new TournamentMatch
                        {
                            MatchIndex = matchIndex++,
                            Scores = new List<TournamentMatchScore>
                            {
                                new TournamentMatchScore
                                {
                                    PreviousMatchIndex = j + matchesCountTotal,
                                    PreviousMatchRank = MatchRank.Loser
                                },
                                new TournamentMatchScore
                                {
                                    PreviousMatchIndex = j + matchesCountTotal + matchesCountRound / 2,
                                    PreviousMatchRank = MatchRank.Winner
                                },
                            }
                        };
                        loserRound.Matches.Add(m);
                    }
                }
            }

            // finals
            if (roundsCount > 1)
            {
                var winnerRound = new TournamentRound
                {
                    Matches = new List<TournamentMatch>(),
                    Order = rounds.Count / 3 + 2,
                    Type = TournamentRoundType.Final
                };
                rounds.Add(winnerRound);

                var m = new TournamentMatch
                {
                    MatchIndex = matchIndex,
                    Scores = new List<TournamentMatchScore>
                    {
                        new TournamentMatchScore
                        {
                            PreviousMatchIndex = matchIndex - 3,
                            PreviousMatchRank = MatchRank.Winner
                        },
                        new TournamentMatchScore
                        {
                            PreviousMatchIndex = matchIndex - 1,
                            PreviousMatchRank = MatchRank.Winner
                        },
                    }
                };
                winnerRound.Matches.Add(m);
            }

            tournament.Rounds = rounds;
        }
    }
}

Answer 4

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.

Answer 5

In normal tournament the games can be placed with the help of a gray-code. Maybe you can use the code also for the second tree. For example create a 2-pass algorithm. You can read about my question here:Gray code pattern in tournament chart?.