Welcome, guest | Sign In | My Account | Store | Cart

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
 1
 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.

1 comment

Nick Perkins 22 years, 9 months ago  # | flag

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!

Created by Andrew Henshaw on Wed, 13 Jun 2001 (PSF)
Python recipes (4591)
Andrew Henshaw's recipes (2)

Required Modules

  • (none specified)

Other Information and Tasks