An implementation of a round-robin algorithm for "fair" pairing of items from a list. The function produces a schedule of the pairings that can occur simultaneously.
Python, 20 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | def roundRobin(units, sets=None):
""" Generates a schedule of "fair" pairings from a list of units """
if len(units) % 2:
units.append(None)
count = len(units)
sets = sets or (count - 1)
half = count / 2
schedule = []
for turn in range(sets):
pairings = []
for i in range(half):
pairings.append(units[i], units[count-i-1])
units.insert(1, units.pop())
schedule.append(pairings)
return schedule
""" test code """
if __name__ == '__main__':
for pairings in roundRobin(range(5)):
print pairings
|
The round-robin pairing algorithm can be used in generating a "fair" list of pairings. The algorithm is often used in competitions, where each competitor should be matched against all of the other competitors, once. In such a case, with N competitors (with N a multiple of 2), there will be N-1 sets of pairings.
If there is an odd number of units in the list, the implementation will add 'None' to the list. The None item will be matched fairly against each of the units. In sports, a competitor paired with 'None', would have a 'bye' for that round.
Tags: algorithms
syntax error. ..easy fix: change: "pairings.append(units[i], units[count-i-1])", on line 12, to: "pairings.append((units[i], units[count-i-1]))", and it works, fine!