I am trying to achieve a round-robin algorithm for sports scheduling that also guarantees a fair or balanced home/away rotation.
I based my algorithm on the round-robin scheduling algorithm:
def round_robin(teams, rounds):
# bye
if len(teams) % 2:
teams.append(None)
schedule = []
for turn in range(rounds):
pairings = []
for i in range(len(teams) / 2):
pairings.append((teams[i], teams[len(teams) - i - 1]))
teams.insert(1, teams.pop())
schedule.append(pairings)
return schedule
However, this algorithm does not address H/A balance. I am trying to satisfy these two objectives:
H/A rotation: each team should play a home game and an away game every other round, i.e. in a tournament with 5 rounds, a given team should have the following rotation:
H-A-H-A-H
.Number of H/A games: the number of home games and away games should be the same (or offset by one if the total is odd) number, so a tournament with 10 games per team should have 5 home games and 5 away games for each team.
The previous algorithm does not satisfy any of these objectives:
It does not alternate H/A games. For example, the first team only has home games, and the other teams get home games until they are rotated to the end of the list and then only away games (and the opposite: away games until reaching the beginning, then get home games only). See what I mean below (1).
It does guarantee a balanced number of H/A games but only if the number of rounds is a multiple of the number of games (or number of games minus one), otherwise we get a number of home or away games too many (the difference between the actual number of games and the next multiple).
(1)
[(1, 8), (2, 7), (3, 6), (4, 5)]
[(1, 7), (8, 6), (2, 5), (3, 4)]
[(1, 6), (7, 5), (8, 4), (2, 3)]
[(1, 5), (6, 4), (7, 3), (8, 2)]
[(1, 4), (5, 3), (6, 2), (7, 8)]
[(1, 3), (4, 2), (5, 8), (6, 7)]
[(1, 2), (3, 8), (4, 7), (5, 6)]
I made several straight forward modifications to get a closer approach to a balanced rotation:
def round_robin(teams, rounds):
# bye
if len(teams) % 2:
teams.append(None)
schedule = []
for turn in range(rounds):
pairings = []
for i in range(len(teams) / 2):
pairing = (teams[i], teams[len(teams) - i - 1])
# alternate first team
if i == 0 and turn % 2:
pairing = pairing[::-1]
# alternate based on the team's previous round appearance
if schedule and None not in pairing:
previous_round = list(sum(schedule[-1], ()))
for team in pairing:
if team in previous_round and pairing[previous_round.index(team) % 2] == team:
pairing = pairing[::-1]
pairings.append(pairing)
teams.insert(1, teams.pop())
schedule.append(pairings)
return schedule
But of course this is not a smart algorithm. It helps, but it does not fully satisfy any of both objectives.
I have been trying to find an algorithm that addresses this issue, but I have not been able to find one, quite a surprise because tournament scheduling is a common problem.
I have thoght of using constraint programming to use this problem, but I am not entirely sure this would be the ultimate solution, maybe it is a bit of an overkill and another most classical approach is better. Also, formulating the problem as a constraint programming problem (or CSP) can turn out to be quite a challenge, at least for me.
Any kind of help, suggestion, insight will be most welcome.