I have 8 teams who have to play each other in a round-robin format, therefore 7 rounds, but only have 4 fields. How can I write a script to allocate fields to games in a fair manner so that any one team only plays on the same field as few times, not in succession, as possible.

3
Contributors
2
Replies
65
Views
5 Years
Discussion Span
Last Post by Gribouillis

8x8 array filled with fields assigned. Could be done with standard search. Assignement is really 3 fields as last is fixed by the third choice. So you have depth three search tree (choosing 2 of 8 teams, 2 of 6 teams and 2 of 4 teams) for each play.

I suggest a recursive search where allocated matches are represented by a list of lists

``````F = [
[(0, 1), (2, 4), (3, 6)],
[(2, 3), (0, 7)],
[(4, 5), (1, 6)],
[(6, 7), (3, 5)]
]
``````

There are 4 rows in this list, each representing a field. Here, F means that in round 0, teams 0 and 1 played in field 0, teams 2 and 3 played in field 1, teams 4, 5 in f. 2, t. 6 and 7 in f. 3.
In round 1, t 2 and 4 played in f. 0, etc.

We suppose by induction that we have a function `solve(F)` which returns a solution of the allocation problem (an array where all 4 rows have length 7, which means that the 7 rounds have been allocated) which rows start with the same elements as the argument array F. The function solve(F) returns None if there is no such solution.

Now here is the pseudo-code for solve() if we look for solutions where each team plays at most twice in each field

``````def solve(F):
n = len(F[0])
if n == len(F[-1]): # all rows have the same length
if n == 7: # we have a solution
return F
else:
x = 0
y = n
else:
x = index of first row with length (n - 1)
y = n - 1
# we try to add a new element in position F[x][y] and call solve() recursively
teams = set(range(8))
remove from teams all teams already in column F[.][y]
remove from teams all teams which appear in position F[x][y-1] (if y > 0)
remove from teams all teams which appear twice in row F[x]
teams = sorted(teams)
pairs = union of set(row) for row in F
F[x].append(None)
for i, a in enumerate(teams):
for b in teams[i+1:]:
if (a, b) in pairs:
continue
F[x][y] = (a, b)
rv = solve(F)
if rv is not None:
return rv
del F[x][-1]
return None
``````

This algorithm can be improved by passing more parameters to solve(). For example the set 'pairs'... or make solve a method of a State class.

Edited by Gribouillis

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.