Skip to content

Instantly share code, notes, and snippets.

@e4c5 e4c5/round_robin.py
Created Feb 2, 2016

Embed
What would you like to do?
A round robing pairing generator where you are control the round in which certain players get the bye or meet certain other players. If a large number of rounds need to be fixed in this manner and they involve players other than the Bye, there is no guarantee that a pairing exists.
class RoundRobin(object):
'''
Usage:
r = RoundRobin(['Bye','Nigel','Wellignton','Andrew','Sherwin','Chollapat','David','Craig'])
r.fix_pairing('Nigel',5, 'Bye')
r.fix_pairing( 'Craig',0,'Bye')
r.brute_force()
'''
def __init__(self,players):
self.players = players
self.num_players = len(self.players)
self.num_rounds = self.num_players
self.games = [[None for x in range(self.num_rounds)] for x in range(self.num_players)]
self.fixed_rounds = [ [] for x in range(self.num_rounds)]
self.matches = 0
def print_table(self, dr = False):
'''
Prints the generated pairing table. If this is a double round robin
tournament set dr = True
'''
sys.stdout.write("{:<10}".format(''))
for rnd in range(1,self.num_players):
if dr:
sys.stdout.write("{:<10}".format('{0},{1}'.format(rnd*2-1,rnd*2)))
else :
sys.stdout.write("{:<10}".format(rnd))
print ''
for i in range(self.num_players):
sys.stdout.write("{:<10}".format(self.players[i]))
for j in self.games[i]:
if j is not None:
if j == -1:
p = 'XX'
else :
p = self.players[j]
sys.stdout.write("{:<10}".format(p))
else :
sys.stdout.write("{:<10}".format('None'))
print ''
def berger_table(self):
'''
Produces a Berger table. Standard pairing with no fixing
'''
rotator = [i for i in range(self.num_players)]
mode = len(rotator)/2
for rnd in range(self.num_rounds):
first = rotator[0:mode]
second = rotator[mode:]
second.reverse()
#print first, second
for idx in range(mode):
player = first[idx]
opponent = second[idx]
self.games[player][rnd] = opponent
self.games[opponent][rnd] = player
popped = rotator.pop()
rotator.insert(1,popped)
def berger_table_with_fixes(self, permutation):
'''
Brute force a solution to the pairing problem.
A solution might not always exists. The possibilities that needs to be
examined grows as N! so for large number it might never complete
'''
self.players = permutation
rotator = [i for i in range(self.num_players)]
mode = len(rotator)/2
for rnd in range(self.num_rounds):
first = rotator[0:mode]
second = rotator[mode:]
second.reverse()
#print first, second
for idx in range(mode):
player = first[idx]
opponent = second[idx]
self.games[player][rnd] = opponent
self.games[opponent][rnd] = player
if self.fixed_rounds[rnd]:
for p,o in self.fixed_rounds[rnd]:
player_idx = self.players.index(p)
opponent_idx = self.players.index(o)
if self.games[player_idx][rnd] != opponent_idx :
return False
popped = rotator.pop()
rotator.insert(1,popped)
self.matches +=1
return True
def fix_pairing(self, player, rnd, opponent):
''' Marks player has having to play opponent in round n '''
self.fixed_rounds[ rnd ].append( (player, opponent) )
def brute_force(self):
'''
Brute force method to find a pairing that meets all player requirements.
'''
i = 0
for perm in permutations(r.players):
i +=1
if self.berger_table_with_fixes( list(perm)):
self.print_table()
break
if i == 100000000:
break
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.