1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – SoBiT May 5 '14 at 13:05
  • $\begingroup$ @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. $\endgroup$ – ubpdqn May 5 '14 at 13:12
  • $\begingroup$ And this solution also avoids duplicated entries, right? $\endgroup$ – SoBiT May 5 '14 at 13:15
  • $\begingroup$ @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. $\endgroup$ – ubpdqn May 5 '14 at 13:28
2
$\begingroup$

You could use LinearProgramming for this. Let the vector of fruits be:

fruits = {
    "Red Pear", "Green Pear", "Yellow Pear", "Red Apple", "Green Apple",
    "Purple Plum", "Red Grapes", "Green Grapes", "Purple Grapes",
    "Blue Bannas", "Yellow Banans"
};

Then,the constraint that there are at least 5 different fruits means that the following matrix must be positive:

{
{1,1,1,0,0,0,0,0,0,0,0},
{0,0,0,1,1,0,0,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,1,1,1,0,0},
{0,0,0,0,0,0,0,0,0,1,1}
}

The constraint that there are at least 5 colors means the following matrix must be positive:

{
{1,0,0,1,0,0,1,0,0,0,0},
{0,1,0,0,1,0,0,1,0,0,0},
{0,0,1,0,0,0,0,0,0,0,1},
{0,0,0,0,0,1,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0,1,0}
}

The objective function will be:

{1,1,1,1,1,1,1,1,1,1,1}

meaning that the number of total fruit is to be minimized (it is possible one might need more than 5). Here is the LinearProgramming call that solves this:

lp = LinearProgramming[
    {1,1,1,1,1,1,1,1,1,1,1},
    {
    {1,1,1,0,0,0,0,0,0,0,0},
    {0,0,0,1,1,0,0,0,0,0,0},
    {0,0,0,0,0,1,0,0,0,0,0},
    {0,0,0,0,0,0,1,1,1,0,0},
    {0,0,0,0,0,0,0,0,0,1,1},
    {1,0,0,1,0,0,1,0,0,0,0},
    {0,1,0,0,1,0,0,1,0,0,0},
    {0,0,1,0,0,0,0,0,0,0,1},
    {0,0,0,0,0,1,0,0,1,0,0},
    {0,0,0,0,0,0,0,0,0,1,0}
    },
    {1,1,1,1,1,1,1,1,1,1},
    0,
    Integers
]

LinearProgramming::lpip: Warning: integer linear programming will use a machine-precision approximation of the inputs.

{0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0}

So, one answer is:

Pick[fruits, lp, 1]

{"Yellow Pear", "Green Apple", "Purple Plum", "Red Grapes", "Blue Bannas"}

$\endgroup$
  • $\begingroup$ Really nice :-) $\endgroup$ – sebhofer Oct 12 '17 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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