If anyone disagrees, here's my implementation of a 'correct' double elimination generator: http://www.mrq3.com/mrcup/dbl_elim.cgi
I'd be interested to know if anyone says that's wrong.
What algorithm are you using for it?
Here's what I came up with, I'd be interested in comparing--it's all Python code but should be pretty easy to understand. I posted an earlier version with some notes at
http://groups.google.com/group/rec.sport.table-soccer/browse_frm/thread/08251a752ad0ca69/484911fcf63e85a5#484911fcf63e85a5Here's the current one:
#
#
#
# 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--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(
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 A1 and A2.
def printBracket(x):
rv = []
splitFactor = 1
reverseFactor = 0
while x > 1:
if splitFactor > x:
splitFactor = x
rv.append(splitAndReverse(range(1,x+1), splitFactor, reverseFactor))
reverseFactor = not reverseFactor
splitFactor *= 2
x /= 2
return rv
for p in printBracket(32):
print p
# that's the end of the code
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.
3 Replies
10972 Views