1047 views

Skip to first unread message

May 23, 2005, 5:12:26 PM5/23/05

to

Posting this here to archive. This is my take at an algorithm for

building the loser's bracket of a double-elimination bracket.

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu