python - Generating natural schedule for a sports league

Question

I'm looking for an algorithm to generate a schedule for a set of teams. For example, imagine a sports season in which each team plays each other, one time as home team and the other as a visitor team on another teams field.

To generate a set of all games in the season is easy, if teams is a list of teams the following would do:

set((x, y) for x in teams for y in teams if x != y)

But I also want to ORDER the games in chronological order in such a way that it satisfies the constraint of a valid game schedule and also looks "naturally random".

The constraint is that the game list should be groupable into a number of rounds where each round consists of n / 2 games (where n is the number of teams) in which each team is paired with another one.

To make the schedule look more natural, two teams should not face each other twice in consecutive rounds. That is, if (a, b) is played in one round, the game (b, a) should not be played in the ext one.

Also, as much as possible every team should play every other round as the away team and the other rounds as the home team. I don't think it is possible to always fulfill this constraint, so it is more a nice to have thing. For instance, one team shouldn't play 8 home games and then 8 away games.

Below is what I got now. The main problem with the algorithm is that it gets stuck in the while-loop quite often. Especially when the number of teams is 16 or more. It also is very inefficient because it builds on using the random sample function and hoping to get it right:

from random import sample
def season_schedule_order(teams, pairs):
    n_games_per_round = len(teams) // 2
    last_pairs = set()
    while pairs:
        r_pairs = set(sample(pairs, n_games_per_round))
        # Check that each team is present once in the round.
        r_teams = set(x for (x, y) in r_pairs) | set(y for (x, y) in r_pairs)
        if r_teams != teams:
            continue
        # Check that two teams doesn't face each other again.
        rev_pairs = set((y, x) for (x, y) in r_pairs)
        if rev_pairs & last_pairs:
            continue
        pairs -= r_pairs
        for p in r_pairs:
            yield p
        last_pairs = r_pairs

teams = set(['aik', 'djurgarden', 'elfsborg', 'gais',
             'gefle', 'hacken', 'halmstad', 'helsingborg'])
pairs = set((x, y) for x in teams for y in teams if x != y)
for (ht, at) in season_schedule_order(teams, pairs):
    print '%-20s %-20s' % (ht, at)

Answer 1

I found a method here which I adapted slightly to this:

def round_robin(units, sets = None):
    """ Generates a schedule of "fair" pairings from a list of units """
    count = len(units)
    sets = sets or (count - 1)
    half = count / 2
    for turn in range(sets):
        left = units[:half]
        right = units[count - half - 1 + 1:][::-1]
        pairings = zip(left, right)
        if turn % 2 == 1:
            pairings = [(y, x) for (x, y) in pairings]
        units.insert(1, units.pop())
        yield pairings

teams = ['a', 'b', 'c', 'd']
print list(round_robin(teams, sets = len(teams) * 2 - 2))

Now I just need to turn this into plpgsql. :)