CODEWITHSUNDEEP
algorithmmatch
elevendollar
elevendollar

Reputation: 1204

Algorithm that matches people based on multiple possible matches

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 of matching them together:

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

Visualised as a graph: enter image description here

Now I want to actually know who to match with each other so that everybody is matched with someone. Ideally no one is left out.

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

A little twist: Also up to 3 people could be matched together.

So based on the example: polyamorous marriage is allowed.

So I can do it manually and get a result that works. So I know that because of {1,2}, {1,5} and {2,5} I can match {1,2,5} together.

Now that means that persons 1,2 and 5 are out, which only leaves the following combinations:

{3,4}, {4,3}

Which leads to {3,4}.

So the final result could be: {1,2,5} and {3,4}

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

Again, visualised as a graph: enter image description here

Now, this is a toy example. It get's much more complicated if the number of people and possible matches goes up.

I am looking for a push in the right direction on how to solve such a problem with a computer.

Upvotes: 4

Views: 1113

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

You can take a somewhat brutal recursive Python function like

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

and memoize it (look up people in a dictionary to see what the output was last time).

Upvotes: 1

Related Questions