Matching two lists of different sizes with exceptions?

Question

Suppose that I have two lists of numbers (which represent IDs for rows in a database):

list1 = [1, 4, 7, 8]
list2 = [2, 3, 5, 6, 7]

I would like to write an algorithm to pair each number in the larger of the two lists with a number in the smaller list such that:

• Every item must appear in at least one pairing
• No item from the larger list appears in more than one pairing
• No item from the smaller list appears more than is necessary to satisfy the first constraint (in other words, if the larger list has 5 members and the smaller list has 3, no item from the smaller list appears more than twice)

The algorithm I came up with is fairly simple (in pseudo-code):

offset_into_smaller_list = 0
foreach item in larger_list
    pairing = [ item, smaller_list[offset_into_smaller_list] ]
    offset_into_smaller_list++
    if offset_into_smaller_list == sizeof(smaller_list)
        offset_into_smaller_list = 0

However, there's a small twist.

I also have a list of exceptions (a pairing that is forbidden).

I would like to modify the algorithm to take these exceptions into account. If one or more valid solutions exists, I'd like the algorithm to find one in the least amount of time possible.

My initial approach began with:

• Calculating all combinations (there are sizeof(list1) * sizeof(list2))
• Removing the exceptions from the list of combinations
• Grouping the combinations using the item in each pair that belongs to the larger list
• Iterating over the groups and selecting one pair from each group

I get stuck at the last step. After each iteration, the number of valid combinations that remain in each group shrinks.

Is there a better approach to this problem? How can I ensure that this algorithm will always find a valid solution if one exists? How can I make it as efficient as possible?

Answer 1

This is an instance of bipartite matching. Build a graph where each left vertex represents one item from the larger list. Duplicate each element in the smaller list the minimum number (e.g., if you want no item from the smaller list to appear more than twice, duplicate each item in the smaller list twice), then use one right vertex for each such (duplicated) item. Draw an edge between items if they are not a forbidden pairing. Then, use any standard algorithm (e.g., the Hungarian algorithm) to search for a perfect matching in this bipartite graph.