Find viable combination from a list of preferences

Question

I have an object that looks like this:

a - ['A', 'B', 'C']
b - ['A', 'B', 'C']
c - ['A', 'B', 'C', 'D']
d - ['A', 'B', 'C', 'D']

each one of the keys has a number of available options as denoted by the list (e.g. a can choose between A, B, C and so on). I want to find a combination of pairs that will satisfy everyone. This could be:

#   Chosen  Remaining          Available Options
------------------------------------------
a - B       - ['A', 'B', 'C'] - ['A', 'B', 'C']
b - A       - ['A', 'C']      - ['A', 'B', 'C']
c - D       - ['C', 'D']      - ['A', 'B', 'C', 'D']
d - C       - ['C']           - ['A', 'B', 'C', 'D']

So in the example above a chose item B, reducing the pool of available options for the remaining participants. b then chose item A, and so on.

I do this by looping through all participants based on how big is the pool of their available choices, the idea being that if I have a participant that wants only one item, then there is no choice but to give him that item, removing it from the pool.

import random

team_choices = {'a': ['A', 'B', 'C'],
                'b': ['A', 'B', 'C'],
                'c': ['A', 'B', 'C', 'D'],
                'd': ['A', 'B', 'C', 'D']}
teams_already_created = []
for team_b in sorted(team_choices, key=team_choices.__getitem__, reverse=False):
    available_opponents = [opponent for opponent in team_choices[team_b] if opponent not in teams_already_created]
    chosen_opponent = random.choice(available_opponents)
    teams_already_created.append(chosen_opponent)

The way I do it though will not always work well since there is no guarantee that at some point it will make a choice that will at a later point choke some other player, leaving him no available options. And if chosen_opponent is empty then obviously this will fail.

Is there a better way of doing this that will work everytime?

Answer 1

This is the problem of finding a maximum matching. There are polynomial-time algorithms (e.g., Hopcroft–Karp).