Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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}};
mp = MapThread[Thread[{#1, #2}] &, {fruit, col}]

where mp gives the candidate selections. Selecting and displaying solutions:

Row[Grid[#, Frame -> True] & /@ 
  Select[Tuples[mp], Sort[#[[All, 2]]] == {b, g, p, r, y} &]]

enter image description here

share|improve this answer
    
Thanks for this answer. I guess I can make it work with this solution, but could you please explain what this script is actually doing? I'd like to understand it and not only use it :) Thanks in advance! –  SoBiT May 5 at 13:05
    
@SoBiT The answer only supplies an approach for the small problem. Tuples[mp] above just generates all the possible combinations choosing each fruit. The core of the second part selects from this list the element which has distinct colours. –  ubpdqn May 5 at 13:12
    
And this solution also avoids duplicated entries, right? –  SoBiT May 5 at 13:15
    
@SoBit I am not sure what you mean by duplicates: the solutions are distinct. The ways lists are created and selected distinct fruits and colours. Would have to change for larger or more complex problem. –  ubpdqn May 5 at 13:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.