Round-robin pairing while referencing previous pairings in Python

Question

While I understand that a round-robin algorithm can be easily used for one-off flows, I need to create a round-robin algorithm which references the results of previous runs, and ensures no duplication of matches over long periods of time.

I am trying to create a script which takes a list of names from a Google Sheet, randomly matches two names at a time, schedules a meeting for those two people and writes the pairing back to the Sheet to keep a history, to make sure the pairing doesn't happen the next time the script is run.

It's effectively a 'round robin' concept where each person is randomly matched with every other person only once. The script runs ~once a week to create a meeting every week.

Here is the overview of the flow:

1. Pull list of names from Sheet
2. Randomly select two names to create a 'pair'
3. Check this pairing hasn't happened before by referencing the Sheet with historical pairings
4. If new pairing, create an event and write the pairing back to the Sheet
5. If not a new pairing, cancel the pair and try again
6. Keep looping until all names are paired, or until one is left/no new pairings possible

I already have code working, but it is very scrappy. My current approach is basically

names = [<names taken from Sheet via API>]

for name in names:
       person1 = random.choice(names)
       names.remove(person1)
       person2 = random.choice(names)
       names.remove(person2)
       match = person1 + "," + person2

<logic for calling Sheets API with current match to make sure it hasn't previously happened>

I have much more code which does the other elements like call different APIs to GET/POST the data, but I'm certain there's a better way to do this.

Currently the script works, but it often fails after once the 'names' list gets down to the final few people, as either all of the remaining people have previously been matched with each other, or there is an odd one out, so an error is thrown which is not properly handled.

Answer 1

I can generally think of a much simpler approach:

• Generate a sequence of all possible pairings
• Select entries from this sequence that contain no duplicates
• Dump all weekly meeting lists at once

So basically, I am suggesting that you make all the lists up-front. This will make the code much simpler, and the results no less random.

from itertools import combinations
from random import shuffle

names = ['A', 'B', 'C', 'D']

options = list(combinations(names, 2))
shuffle(options)

def make_week(options):
    week = []
    remainder = []
    seen = set()
    for p1, p2 in options:
        if p1 not in seen and p2 not in seen:
            week.append((p1, p2))
            seen.add(p1)
            seen.add(p2)
        else:
            remainder.append((p1, p2))
    return week, remainder

remainder = options
while len(remainder) >= len(names) // 2:
    week, remainder = make_week(remainder)
    # Dump the list for that week

Notice that we only need to shuffle once: remainder preserves the order of the original list. This version assumes that your list of names won't change week-to-week. If it does, you can use most of the same concepts to generate next week's schedule.

For example, let's say you loaded last week's meetings as a list of two-tuples containing the names:

last_week = [('B', 'D'), ('A', 'C')]

You can remove the elements of last_week from a set of valid options. To avoid having to check for both combinations, ensure that names is sorted first:

names.sort()
options = set(combinations(names, 2))
for item in last_week:
    options.remove((min(item), max(item)))
options = list(options)
shuffle(options)