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.
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)}