Code works fine except...
John Yeung
gallium.arsenide at gmail.com
Tue May 5 23:16:41 EDT 2009
On May 5, 10:49 am, Ross <ross.j... at gmail.com> 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):
self.id = id
self.played = []
self.latency = 0
def __str__(self):
str(self.id)
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
first
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
playerlist.sort()
for i in range(players - 1):
for j in range(i + 1, players):
candidate = tuple(sorted((playerlist[i].id, playerlist
[j].id)))
if candidate in matchlist:
yield matchlist.pop(matchlist.index(candidate))
for p in playerlist:
if p.id == candidate[0]:
p.played.append(candidate[1])
p.latency = 0
elif p.id == candidate[1]:
p.played.append(candidate[0])
p.latency = 0
else:
p.latency += 1
found = True
break
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