Double-elimination loser's bracket scheduling algorithm
sjde...@yahoo.com
building the loser's bracket of a double-elimination bracket.
It's all python code (http://www.python.org)
Some gotchas if you're reimplementing:
Notice that the recursive call keeps toggling reverseFactor (calls are
made with a value of "not reverseFactor" to toggle it)
If you just want to find the values for the n'th round out, then:
reverseFactor = 1 if n is even, 0 if n is odd
splitFactor = 2^(n-1)
The "range" function is just generating a list; range(1, 8) is a Python
function that returns the list [ 1,2,3,4,5,6,7,8 ].
The + operator concatenates lists, so [1,2] + [3,4] returns the list
[1,2,3,4].
Output for printBracket(32) is:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]
[9, 10, 11, 12, 13, 14, 15, 16, 1, 2, 3, 4, 5, 6, 7, 8]
[3, 4, 1, 2, 7, 8, 5, 6]
[3, 4, 1, 2]
[1, 2]
(Note that the [3,4,1,2] looks suspicious lining up under
[3,4,1,2,7,8,5,6] but it's actually pairing C3 against B3 and C4
against B4, which puts players from the bottom half of the C round
playing against players from the top half of the B round).
Here's the code:
# This function recursively splits and reverses the bracket, recursing
# until the splitFactor is 1.
#
# someList is the list that you want to split.
#
# splitFactor is a recursive number set up by printBracket; it just
# doubles for every round you go out in the bracket. Intuitively,
# it is the number of "mini-lists" that you are splitting the main list
# into. So if [0,1,2,3,4,5,6,7] is going to become
# [2,3,0,1,6,7,4 5]), you have essentially split the original into
# 4 little segments of consecutive numbers [2,3], [0,1], [6,7], [4,5],
# --so splitFactor was 4 to generate this list.
#
# reverseFactor is whether or not to reverse the order of the matches
# inside each little split list.
def splitAndReverse(someList, splitFactor, reverseFactor):
if splitFactor == 1:
return someList
# left and right are the left and right halves of
# someList. So if someList is [0,1,2,3,4,5,6,7], then
# left is [0,1,2,3] and right is [4,5,6,7]
left = someList[:len(someList)/2]
right = someList[len(someList)/2:]
if reverseFactor:
return splitAndReverse(right, splitFactor/2, not reverseFactor)
+ \
splitAndReverse(left, splitFactor/2, not reverseFactor)
else:
return splitAndReverse(left, splitFactor/2, not reverseFactor)
+ \
splitAndReverse(right, splitFactor/2, not reverseFactor)
#
# This function prints the permutations for a bracket of the given
size.
# The size is actually the number of matches in the first round of the
# losers bracket, so calling printBracket( 8 ) will print out the
permutations
# for a 32-team bracket (which had 16 matches in the first round of the
# winner's bracket and has 8 matches in the first round of the loser's
# bracket)
#
# The lists printed out are the ordering of the matches
# from the winner's side. These are often labelled as A1....An for the
# second round of the winner's bracket, B1...Bn/2 for the third round,
# etc (the first round of the winner's bracket is often not given a
letter)
# I don't print the letters here, just the whole ordering for the
loser's
# bracket tree. So (example here is a 16-team bracket) if it prints:
#
# [1, 2, 3, 4, 5, 6, 7, 8]
# [3, 4, 1, 2]
# [1, 2]
# That means that the first round in the loser's bracket is just the
losers
# of the opening 8 rounds (this is just the first "move losers to the
left
# of the center" step)
# The next round is [3,4,1,2]; the fill-ins for the loser's bracket
round
# that takes 4 new teams should be from top to bottom
# the losers of A3, A4, A1, A2 in the winner's side.
# The next round is [1,2]; the fill-ins for the round should be the
losers
# of B1 and B2.
#
# Call with a bigger value of X to see bigger results.
def printBracket(x):
splitFactor = 1
reverseFactor = 0
print "*** displaying ", x
while x > 1:
if splitFactor > x:
splitFactor = x
print splitAndReverse(range(1,x+1), splitFactor, reverseFactor)
reverseFactor = not reverseFactor
splitFactor = splitFactor * 2
x = x / 2
printBracket( 8 )
This code is copyright 2005, Gerry Sumner Hayes. All rights reserved.
This code is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied
warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU General Public License for more details.