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?