Using Python to model a single elimination tournament

Question

I'm learning python and I want to model a single elimination tournament like they use in athletic events like tennis, basketball, etc. The idea would be to insert some meaningful metrics to determine the winner. I've already got a database that I plan to connect to to get the metrics, but I am hoping to find a better way to "process" games in the tournament to move the winner to the next round, and eventually find the tournament winner.

So far this is the best I have come up with, but it doesn't scale (at all easily) to 32, 64, 128 entries & so-on. The "primary key" that I need to retain is the "seed id" (1-16, in this case), which matches the unique identifier in the database, so that I can pull the correct metrics for deciding which entry will win a matchup. Suggestions?

## this list represents the round 1 seeding order on the tournament sheet
## this doesnt easily scale to 32, 64, 128 entries
teamlist = [1,16,8,9,5,12,4,13,6,11,3,14,7,10,2,15]  

#In a single elim tournament with a full field, # of games is # of teams-1
totalgames = len(teamlist) - 1

#Set defaults
gameid = 0
roundid = 0
nextround = []

#simulate all of the games
while gameid < totalgames:
    if gameid in [8,12,14]:  ##this is a manual decision tree, doesn't scale at all
        #if a new round begins, reset the list of the next round
        print "--- starting a new round of games ---"
        teamlist = nextround
        nextround = []
        roundid = 0

    #compare the 1st entry in the list to the 2nd entry in the list
    homeid = teamlist[roundid]
    awayid = teamlist[roundid + 1]

    #the winner of the match become the next entry in the nextround list
    #more realistic metrics could be substituted here, but ID can be used for this example
    if homeid < awayid:
        nextround.append(homeid)
        print str(homeid) + " vs " + str(awayid) + ":  The winner is " + str(homeid)
    else:
        nextround.append(awayid)
        print str(homeid) + " vs " + str(awayid) + ":  The winner is " + str(awayid)

    #increase the gameid and roundid
    gameid += 1
    roundid += 2
    print "next round matchup list: " + str(nextround)

print nextround

Answer 1

You have two lines marked as "doesn't scale".

The initial team list can be obtained from your database table of available teams (select of team details).

The other "problem line", is

 if gameid in [8,12,14]:  ##this is a manual decision tree, doesn't scale at all

But that's easily avoided by noticing that the games in a round are always half the previous round, and the initial round is half the number of teams!

In other words, you can do something like (if you include the initial round):

def NewRoundIds( teams_in_tournament ):
    round_ids = []
    game_id = 0
    games_in_next_round = len(teams_in_tournament)/2 #need to count the number of teams_in_tournament list
    while games_in_next_round > 0:
        round_ids += [game_id]
        game_id += games_in_next_round
        games_in_next_round /= 2
    return round_ids

new_round_game_ids = NewRoundIds( teamlist )
...
if gameid in new_round_game_ids:
    # etc

== edit ==

This puts it well outside the brief of the site, but it was interesting. The following I think does what you want, generate_tournament(16). It could do with a bit of tidying up, and it's the sort of thing that will certainly benefit from docstrings and doctests, which I shall leave as a exercise.

import math

def tournament_round( no_of_teams , matchlist ):
    new_matches = []
    for team_or_match in matchlist:
        if type(team_or_match) == type([]):
            new_matches += [ tournament_round( no_of_teams, team_or_match ) ]
        else:
            new_matches += [ [ team_or_match, no_of_teams + 1 - team_or_match ] ]
    return new_matches

def flatten_list( matches ):
    teamlist = []
    for team_or_match in matches:
        if type(team_or_match) == type([]):
            teamlist += flatten_list( team_or_match )
        else:
            teamlist += [team_or_match]
    return teamlist

def generate_tournament( num ):
    num_rounds = math.log( num, 2 )
    if num_rounds != math.trunc( num_rounds ):
        raise ValueError( "Number of teams must be a power of 2" )
    teams = 1
    result = [1]
    while teams != num:
        teams *= 2
        result = tournament_round( teams, result )
    return flatten_list( result )