Code works fine except...

John Yeung gallium.arsenide at
Tue May 5 23:16:41 EDT 2009

On May 5, 10:49 am, Ross <ross.j... at> wrote:
> I'm interested to see what you did. From your description,
> it sounds like I've tried what you've done, but when I
> implemented my version, it took minutes to evaluate for
> bigger numbers. If that isn't the case with yours, I'd be
> interested in seeing your implementation.

I don't know how big your "bigger numbers" are, but this should run in
a reasonable time.  It helps if you are using Python 2.6.  If not, you
should go on-line to the itertools docs to get the pure-Python
equivalent for itertools.combinations.

Since no matches are "thrown away", the byes are expressed simply as a
list of players that have to sit out for the week.

A couple of the lines are on the longish side, so beware of wrapping
from the browser/newsreader.

# Let's just try choosing from the possible combinations, each week
# scheduling those who have played the least or waited the longest.

import itertools

class Player(object):
    def __init__(self, id): = id
        self.played = []
        self.latency = 0

    def __str__(self):

    def __cmp__(self, other):
        if len(self.played) != len(other.played):
            return len(self.played) - len(other.played)
        return other.latency - self.latency # select longer latency

def flattened(listOfLists):
    return list(itertools.chain(*listOfLists))

def pairings(players):
    idlist = range(players)
    playerlist = [Player(i) for i in idlist]
    matchlist = list(itertools.combinations(idlist, 2))
    while matchlist:
        found = False
        for i in range(players - 1):
            for j in range(i + 1, players):
                candidate = tuple(sorted((playerlist[i].id, playerlist
                if candidate in matchlist:
                    yield matchlist.pop(matchlist.index(candidate))
                    for p in playerlist:
                        if == candidate[0]:
                            p.latency = 0
                        elif == candidate[1]:
                            p.latency = 0
                            p.latency += 1
                    found = True
            if found: break

def schedule(players, weeks, courts):
    playerlist = range(players)
    matchlist = list(pairings(players))
    cap = min(courts, players // 2)
    start = 0
    for week in range(weeks):
        matches = matchlist[start:start + cap]
        byes = set(playerlist) - set(flattened(matches))
        print matches, list(byes)
        start += cap

More information about the Python-list mailing list