基于多个可能的匹配匹配人的算法

Question

假设我有一组 5 个人 P = {1, 2, 3, 4, 5} 并且我知道有以下将他们匹配在一起的可能性:

{1,2}, {1,3}, {1,5}, {2,1}, {2,4}, {2,5}, {3,1}, {3,4}, {4,2}, {4,3}, {4,5}, {5,1}, {5,2}, {5,4}

For example they could symbolise who likes who (everyone is bisexual, gender doesn't matter).

可视化为图表:

现在我想真正知道要与谁匹配，以便每个人都与某人匹配。理想情况下，没有人会被排除在外。

So based on the example: Who should get married with whom? Ideally no one should stay single.

一点点变化:最多也可以匹配 3 个人。

So based on the example: polyamorous marriage is allowed.

所以我可以手动完成并获得有效的结果。所以我知道因为 {1,2}、{1,5} 和 {2,5} 我可以匹配 {1,2,5} 在一起。

现在这意味着第 1、2 和 5 个人出局了，只剩下以下组合:

{3,4}, {4,3}

这导致 {3,4}。

所以最终结果可能是:{1,2,5} 和 {3,4}

So based on the example: Person 1, 2 and 5 get married and person 3 and 5 get married.

再次，可视化为图形:

现在，这是一个玩具示例。如果人数和可能的匹配项增加，事情就会变得更加复杂。

我正在寻找有关如何使用计算机解决此类问题的正确方向。

Answer 1

你可以采用有点残酷的递归 Python 函数，比如

# people is a frozenset
# conflicts is a set of frozenset pairs
def match(people, conflicts):
    if not people:  # people is empty
        return {}
    for group in next_groups(people, conflicts):
        solution = match(people - group, conflicts)
        if solution is not None:
            solution.add(group)
            return solution
    return None


def next_groups(people, conflicts):
    a = min(people)
    for b in people - {a}:
        if frozenset({a, b}) in conflicts:
            continue
        yield frozenset({a, b})
        for c in people - {a, b}:
            if frozenset({a, c}) in conflicts or frozenset({b, c}) in conflicts:
                continue
            yield frozenset({a, b, c})

并记住它(在字典中查找 people 以查看上次输出的内容)。