Find most efficient groups of pairs : <h2>Problem</h2>

<p>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:</p>

<ol>
<li>Find every possible pairing combination</li>
<li>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.</li>
</ol>

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

<pre><code>&gt;&gt;&gt; people = ['Dave', 'Mary', 'Susan', 'John']
</code></pre>

<p>I want to produce the following output:</p>

<pre><code>&gt;&gt;&gt; for round in make_rounds(people):
&gt;&gt;&gt;     print(round)
[('Dave', 'Mary'), ('Susan', 'John')]
[('Dave', 'Susan'), ('Mary', 'John')]
[('Dave', 'John'), ('Mary', 'Susan')]
</code></pre>

<p>If I had an odd number of people, then I would expect this result:</p>

<pre><code>&gt;&gt;&gt; people = ['Dave', 'Mary', 'Susan']
&gt;&gt;&gt; for round in make_rounds(people):
&gt;&gt;&gt;     print(round)
[('Dave', 'Mary')]
[('Dave', 'Susan')]
[('Mary', 'Susan')]
</code></pre>

<p>The key to this problem is that I need my solution to be performant (within reason). I've written code that <em>works</em>, but as the size of <code>people</code> 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</p>

<h2>What I've tried</h2>

<p>Step 1 is easy: I can get all possible pairings using <code>itertools.combinations</code>:</p>

<pre><code>&gt;&gt;&gt; from itertools import combinations
&gt;&gt;&gt; people_pairs = set(combinations(people, 2))
&gt;&gt;&gt; print(people_pairs)
{('Dave', 'Mary'), ('Dave', 'Susan'), ('Dave', 'John'), ('Mary', 'Susan'), ('Mary', 'John'), ('Susan', 'John')}
</code></pre>

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

<ol>
<li>Create an empty <code>round</code> list</li>
<li>Iterate over a copy of the <code>people_pairs</code> set calculated using the <code>combinations</code> method above</li>
<li>For each person in the pair, check if there are any existing pairings inside the current <code>round</code> that already contain that individual</li>
<li>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 <code>people_pairs</code> list.</li>
<li>Once all the people pairs have been iterated over, append the round to a master <code>rounds</code> list</li>
<li>Start again, since <code>people_pairs</code> now contains only the pairs that didn't make it into the first round</li>
</ol>

<p>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.</p>

<p>Here's my code:</p>

<pre><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
</code></pre>

<p>Plotting out the performance of this method for list sizes of 100-300 using <a href="https://mycurvefit.com" rel="noreferrer">https://mycurvefit.com</a> 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?</p>

<p>Note: I'm not <em>actually</em> 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. </p>
