Find most efficient groups of pairs

Question

Problem

I have a group of people, and I want each person to have a 1:1 meeting with every other person in the group. A given person can only meet with one other person at a time, so I want to do the following:

1. Find every possible pairing combination
2. Group pairs together into "rounds" of meetings, where each person can only be in a round once, and where a round should contain as many pairs as possible to satisfy all possible pairing combinations in the smallest number of rounds.

To demonstrate the problem in terms of desired input/output, let's say I have the following list:

>>> people = ['Dave', 'Mary', 'Susan', 'John'] 

I want to produce the following output:

>>> for round in make_rounds(people): >>>     print(round) [('Dave', 'Mary'), ('Susan', 'John')] [('Dave', 'Susan'), ('Mary', 'John')] [('Dave', 'John'), ('Mary', 'Susan')] 

If I had an odd number of people, then I would expect this result:

>>> people = ['Dave', 'Mary', 'Susan'] >>> for round in make_rounds(people): >>>     print(round) [('Dave', 'Mary')] [('Dave', 'Susan')] [('Mary', 'Susan')] 

The key to this problem is that I need my solution to be performant (within reason). I've written code that works, but as the size of people grows it becomes exponentially slow. I don't know enough about writing performant algorithms to know whether my code is inefficient, or whether I'm simply bound by the parameters of the problem

What I've tried

Step 1 is easy: I can get all possible pairings using itertools.combinations:

>>> from itertools import combinations >>> people_pairs = set(combinations(people, 2)) >>> print(people_pairs) {('Dave', 'Mary'), ('Dave', 'Susan'), ('Dave', 'John'), ('Mary', 'Susan'), ('Mary', 'John'), ('Susan', 'John')} 

To work out the rounds themselves, I'm building a round like so:

1. Create an empty round list
2. Iterate over a copy of the people_pairs set calculated using the combinations method above
3. For each person in the pair, check if there are any existing pairings inside the current round that already contain that individual
4. If there's already a pair that contains one of the individuals, skip that pairing for this round. If not, add the pair to the round, and remove the pair from the people_pairs list.
5. Once all the people pairs have been iterated over, append the round to a master rounds list
6. Start again, since people_pairs now contains only the pairs that didn't make it into the first round

Eventually this produces the desired result, and whittles down my people pairs until there are none left and all the rounds are calculated. I can already see that this is requiring a ridiculous number of iterations, but I don't know a better way of doing this.

Here's my code:

from itertools import combinations  # test if person already exists in any pairing inside a round of pairs def person_in_round(person, round):     is_in_round = any(person in pair for pair in round)     return is_in_round  def make_rounds(people):     people_pairs = set(combinations(people, 2))     # we will remove pairings from people_pairs whilst we build rounds, so loop as long as people_pairs is not empty     while people_pairs:         round = []         # make a copy of the current state of people_pairs to iterate over safely         for pair in set(people_pairs):             if not person_in_round(pair[0], round) and not person_in_round(pair[1], round):                 round.append(pair)                 people_pairs.remove(pair)         yield round 

Plotting out the performance of this method for list sizes of 100-300 using https://mycurvefit.com shows that calculating rounds for a list of 1000 people would probably take around 100 minutes. Is there a more efficient way of doing this?

Note: I'm not actually trying to organise a meeting of 1000 people :) this is just a simple example that represents the matching / combinatorics problem I'm trying to solve.

Answer 1

This is an implementation of the algorithm described in the Wikipedia article Round-robin tournament.

from itertools import cycle , islice, chain  def round_robin(iterable):     items = list(iterable)     if len(items) % 2 != 0:         items.append(None)     fixed = items[:1]     cyclers = cycle(items[1:])     rounds = len(items) - 1     npairs = len(items) // 2     return [         list(zip(             chain(fixed, islice(cyclers, npairs-1)),             reversed(list(islice(cyclers, npairs)))         ))         for _ in range(rounds)         for _ in [next(cyclers)]     ] 

Answer 2

I generate just the indices (because I have trouble coming up with 1000 names =), but for 1000 numbers the runtime is about 4 seconds.

The main problem of all other approaches -- they use pairs and work with them, there are plenty of pairs, and the run time is getting much longer. My approach differs in working with people, not pairs. I have a dict() that maps the person to the list of other persons (s)he has to meet, and these lists are at most N items long (not N^2, as with pairs). Hence the time savings.

#!/usr/bin/env python  from itertools import combinations from collections import defaultdict  pairs = combinations( range(6), 2 )  pdict = defaultdict(list) for p in pairs :     pdict[p[0]].append( p[1] )  while len(pdict) :     busy = set()     print '-----'     for p0 in pdict :         if p0 in busy : continue          for p1 in pdict[p0] :             if p1 in busy : continue              pdict[p0].remove( p1 )             busy.add(p0)             busy.add(p1)             print (p0, p1)              break      # remove empty entries     pdict = { k : v for k,v in pdict.items() if len(v) > 0 }  ''' output: ----- (0, 1) (2, 3) (4, 5) ----- (0, 2) (1, 3) ----- (0, 3) (1, 2) ----- (0, 4) (1, 5) ----- (0, 5) (1, 4) ----- (2, 4) (3, 5) ----- (2, 5) (3, 4) '''