# How do I find the all valid pairings between two sets?

I have a pretty hard problem to solve here, and I have no idea how to start. I have X kind of fruits and 5 colors (let's say Red, Green, Yellow, Blue and Purple). Each fruit can be available in several colors (but in at least 1). How can I find each combination, when I need exactly 1 fruit of each color but no fruit twice (so there will always be bought exaclty 5 fruits in exactly 5 different colors)?

For example:

1. Pears are available in [Red, Green, Yellow]
2. Apples are available in [Red, Green]
3. Plums are available in [Purple]
4. Grapes are available in [Red, Green, Purple]
5. Bananas are available in [Blue, Yellow]

Since bananas are the only fruit available in blue, it's already sure, that bananas will be bought in blue, and not in yellow.

These would be the solution for this list:

1. Yellow Pear, Red Apple, Purple Plum, Green Grapes, Blue Banana
2. Yellow Pear, Green Apple, Purple Plum, Red Grapes, Blue Banana

No other combination is possible here. Is there any algorithm to do this with a dynamic list, which may also have more than 5 fruits?

I know, it's a pretty hard problem, but maybe someone has a simple solution for it.

-

You could do this small size problem with brute force:

fruit = {pear, apple, plum, grape, banana};
col = {{r, g, y}, {r, g}, {p}, {r, g, p}, {b, y}};

where mp gives the candidate selections. Selecting and displaying solutions:
Row[Grid[#, Frame -> True] & /@