An algorithm that matches people based on several possible matches

Question

Let's say I have a set of 5 people P = {1, 2, 3, 4, 5}, and I know that there are the following possibilities for comparing them:

{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 can symbolize who loves whom (all bisexual, gender does not matter).

It is visualized as a graph:

Now I want to know who should coincide with each other so that everyone is similar to someone. Ideally, no one was left.

So, for example: who should marry whom? Ideally, no one should be alone.

Small twist: You can also match up to 3 people.

So, for example: polyamoral 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}

, : 1, 2 5 3 5 .

, :

. , .

, .

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