python - 根据与谁兼容来匹配组中人员的算法

Question

我试图根据他们的兼容性在一群人中找到最大的匹配。当我意识到我没有 2 个不同的组时，我正朝着二分图上的最大基数匹配前进。

我在哪里：

我有他们的 ID 列表：[1, 8, 3, 15, 13, 21]

我有一个名为 verify 的函数，它将验证 2 个 id 是否兼容（可能是奇数）。

然后我创建每个人索引兼容的索引图（字典）：

    ids = [1, 8, 3, 15, 13, 21]
    l = len(ids)
    matches = {}
    for x in range(l):
        matches.setdefault(x,[])
        for y in range(l):
            if x != y:
                if verify(ids[x],ids[y]):
                    matches[x].append(y)

这会产生：

{0: [3, 4, 5], 1: [2, 4, 5], 2: [1, 5], 3: [0, 4, 5], 4: [0, 1, 3], 5: [0, 1, 2, 3]}

现在我不确定从这里去哪里，或者我是否应该采取另一个方向。

有人可以指出我正确的方向吗？谢谢

标签： pythonalgorithmmatching

Answer 1

看起来你正在尝试解决稳定的婚姻问题。我编写了一个Rosetta Code 任务，其中包含 Python 和其他语言的解决方案。