如何编写高效的配对算法？

Question

我需要一种算法的帮助，该算法可以有效地将人们分组，并确保以前的配对不会重复。

例如，假设我们有 10 位候选人；

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

并假设我们有一个先前匹配的字典，使得每个键值对 iecandidate:matches代表一个候选者和迄今为止与它们配对的候选者数组；

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]}

因此，对于Candidate 0，它们首先与 、 、 和 配对，在随后的配对轮中，它们与、、 和Candidate 6配对。字典中的其他键值对也是如此。Candidate 5Candidate 1Candidate 2

从所有比赛的时长可以看出，已经进行了四轮比赛prev_matches。如何编写一个算法来创建第五、第六...第 n（最多 numberOfCandidates - 1）轮比赛，​​以使候选人没有重复对？

因此Candidate 0不能再与Candidate 6、Candidate 5、Candidate 1和配对Candidate 2。在可能的第五轮比赛之后，我们可以 prev_matches这样：

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]}。

这是我尝试过的一个简单的解决方案：

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

它在第五轮工作并返回以下结果：

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]}

然而，在第六轮中，它失败了，因为一些候选者（7 和 8）找不到有效的配对：

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]}

因此，它既不是可靠的也不可接受的解决方案。

我正在考虑将其视为回溯问题，以便我在各轮中探索所有可能的配对，直到在第 n 轮后达到完全可接受且有效的解决方案。但这里关注的是如何使其有效地运作。

如果我能得到任何帮助，我将不胜感激。

Answer 1

如果你从一开始就负责比赛，那么最简单的解决方案就是按照循环赛的方式组织配对。

如果您无法控制第一轮的配对，并且必须组织后续轮次，那么这里有一个使用模块 networkx 来计算图中的最大匹配的解决方案：

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)

输出：

{(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)}