How do I write an efficient Pair Matching algorithm?

Question

I need help with an algorithm that efficiently groups people into pairs, and ensures that previous pairs are not repeated.

For example, say we have 10 candidates;

candidates = [0,1,2,3,4,5,6,7,8,9]

And say we have a dictionary of previous matches such that each key-value pair i.e. candidate:matches represents a candidate and an array of candidates that they have been paired with so far;

prev_matches = {0: [6, 5, 1, 2], 1: [4, 9, 0, 7], 2: [9, 8, 6, 0], 3: [5, 4, 8, 9], 4: [1, 3, 9, 6], 5: [3, 0, 7, 8], 6: [0, 7, 2, 4], 7: [8, 6, 5, 1], 8: [7, 2, 3, 5], 9: [2, 1, 4, 3]}

So for Candidate 0, they were first paired with Candidate 6, and in the subsequent pairing rounds, they were paired with Candidate 5, Candidate 1, and Candidate 2. The same follows for the other key-value pairs in the dictionary.

There have already been four rounds of matches, as indicated by the length of all the matches in prev_matches. How do I script an algorithm that creates a fifth, sixth...nth(up to numberOfCandidates - 1) round of matches such that candidates do not have duplicate pairs?

So Candidate 0 can no longer be paired with Candidate 6, Candidate 5, Candidate 1, and Candidate 2. And after a possible fifth round of matches, we could have our prev_matches as such:

prev_matches: {0: [6, 5, 1, 2, 3], 1: [4, 9, 0, 7, 2], 2: [9, 8, 6, 0, 1], 3: [5, 4, 8, 9, 0], 4: [1, 3, 9, 6, 7], 5: [3, 0, 7, 8, 9], 6: [0, 7, 2, 4, 8], 7: [8, 6, 5, 1, 4], 8: [7, 2, 3, 5, 8], 9: [2, 1, 4, 3, 5]}.

Here is a naive solution I tried:

def make_match(prev_matches):
    paired_candidates = set()
    for candidate, matches in prev_matches.items():
        i = 0
        while i < 10:
            if i != candidate and i not in matches and i not in paired_candidates and candidate not in paired_candidates:
                prev_matches[candidate].append(i)
                prev_matches[i].append(candidate)
                paired_candidates.add(candidate)
                paired_candidates.add(i)
                break
            i += 1
    return prev_matches

It worked for the fifth round and returned the following:

prev_matches = {0: [6, 5, 1, 2, 3], 1: [4, 9, 0, 7, 2], 2: [9, 8, 6 0, 1], 3: [5, 4, 8, 9, 0], 4: [1, 3, 9, 6, 5], 5: [3, 0, 7, 8, 4], 6: [0, 7, 2, 4, 8], 7: [8, 6, 5, 1, 9], 8: [7, 2, 3, 5, 6], 9: [2, 1, 4, 3, 7]}

For the sixth round however, it failed to work as some candidates (7 and 8) couldn't find valid pairs:

prev_matches = {0: [6, 5, 1, 2, 3, 4], 1: [4, 9, 0, 7, 2, 3], 2: [9, 8, 6, 0, 1, 5], 3: [5, 4, 8, 9, 0, 1], 4: [1, 3, 9, 6, 5, 0], 5: [3, 0, 7, 8, 4, 2], 6: [0, 7, 2, 4, 8, 9], 7: [8, 6, 5, 1, 9], 8: [7, 2, 3, 5, 6], 9: [2, 1, 4, 3, 7, 6]}

As such, it's neither a reliable nor acceptable solution.

I'm considering treating it as a backtracking problem such that I'd explore all possible pairings across the rounds till I reach a wholly acceptable and valid solution after the nth round. But the concern here would be how to make it work efficiently.

I'd appreciate any help I can get.

@Woodford, .. which will return 45 (`10! / 2! * (10 - 2)!`) pairs which is definitely not enough to form even five unique pairs for each element. — Olvin Roght, Jan 04 '22 at 18:25
Append the list of candidates to itself then use a sliding window with increasing width to pair the candidates — JonSG, Jan 04 '22 at 18:39
To clarify - someone other than you has already made the first four rounds of matches, and you are only in charge of the remaining rounds? Because there is a very simple solution if you are in charge of all rounds from the beginning. — Stef, Jan 04 '22 at 23:17
Related questions: [Get n * k unique sets of 2 from list of length n in Python](https://stackoverflow.com/a/64606498/3080723); [How to split a list into pairs in all possible ways](https://stackoverflow.com/a/13020502/3080723) — Stef, Jan 04 '22 at 23:25
Also probably useful: [networkx.max_weight_matching](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.matching.max_weight_matching.html) — Stef, Jan 04 '22 at 23:26

Stef · Accepted Answer · 2022-09-02T10:21:02.943

If you are in charge of the tournament from the beginning, then the simplest solution is to organise the pairings according to a round-robin tournament.

If you have no control on the pairings of the first rounds, and must organise the following rounds, here is a solution using module networkx to compute a maximum matching in a graph:

from networkx import Graph
from networkx.algorithms.matching import max_weight_matching, is_perfect_matching

def next_rounds(candidates, prev_matches):
    G = Graph()
    G.add_nodes_from(candidates)
    G.add_edges_from((u,v) for u,p in prev_matches.items() for v in candidates.difference(p).difference({u}))
    m = max_weight_matching(G)
    while is_perfect_matching(G, m):
        yield m
        G.remove_edges_from(m)
        m = max_weight_matching(G)

for r in next_rounds({0,1,2,3,4,5,6,7,8,9},
                     {0: [6, 5, 1, 2], 1: [4, 9, 0, 7], 2: [9, 8, 6, 0], 3: [5, 4, 8, 9], 4: [1, 3, 9, 6],  5: [3, 0, 7, 8], 6: [0, 7, 2, 4], 7: [8, 6, 5, 1], 8: [7, 2, 3, 5], 9: [2, 1, 4, 3]}):
    print(r)

Output:

{(2, 7), (8, 1), (0, 9), (4, 5), (3, 6)}
{(2, 4), (3, 7), (8, 0), (9, 5), (1, 6)}
{(0, 7), (8, 4), (1, 5), (9, 6), (2, 3)}
{(9, 7), (0, 4), (8, 6), (2, 5), (1, 3)}
{(1, 2), (0, 3), (8, 9), (5, 6), (4, 7)}

thank you. Say I was in charge of all the rounds from the beginning as you asked in one of your comments, how would you propose I go about it? — Wolemercy, Jan 08 '22 at 19:06
@Wolemercy With a [round-robin tournament](https://stackoverflow.com/a/64606498/3080723) — Stef, Jan 09 '22 at 10:53

How do I write an efficient Pair Matching algorithm?

1 Answers1

Linked