CODEWITHSUNDEEP
algorithmcombinationscombinatorics
SoBiT
SoBiT

Reputation: 408

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

First of all: It doesn't matter in which programming language you can solve this, it will be easy for me to convert it to any other.

I have a pretty hard problem to solve here, and I have no idea how to start. I have X kind of fruits and EXACTLY 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 exactly 5 different 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.

Upvotes: 1

Views: 186

Answers (1)

Codor
Codor

Reputation: 17605

To my understanding, the problem can be modelled as a bipartite matching problem; here the colors would constitute one partition while the fruits constitute the other partition. an edge between color c and fruit f exists if and only if fruit f is available in color c. The objective is to cover all colors.

Upvotes: 1

Related Questions