Algorithm to pick sets to equal a given input of colored balls of different amounts

Question

I have a specific problem and I am kind of stuck. Don't know exactly where to begin defining what it is. Is someone could just give me a nodge in the right direction or even better, tell me what kind of problem it is, that would be nice. I can of course do the hard work myself but right now I need some help figuring out what to google basically.

The problem is like this, it involves balls of different colors and amounts.

Given something along the lines of this:

3 red balls
2 green balls
1 blue ball

I want to find combinations of the sets below that together contain exactly the combinations of balls that are given. There can be a lot of balls of other colors and I don't care about them.

The data to choose from looks like this:

Set 1 2 red 1 blue 2 yellow

Set 2 1 red 1 blue 3 purple

Set 3 1 purple 1 green

Set 4 1 red 1 green

Set 5 1 red 1 blue 2 greens 3 brown

A possible solution would be this:

Set 1 + Set 3 + Set 4 is a valid solution. It adds up to this:

3 red 1 blue 2 green 2 yellow 1 purple

Which contains the given specification, again, the amounts of balls contained within the solution that is of a color that is not in the given specification is not a problem. There can be multiple solutions, for example Set 1 + Set 5 is also a valid solution and I want to find that as well. There is no need to constraint to a specific amount of sets to be chosen, unless that is easier of course.

What kind of problem is this and what can be used to find the solutions?

Thanks in advance!

Answer 1

First, find every possible combination of sets that satisfy the requirement for number of red balls. For your example, these are:

$S_1 = \{1, 2\}$

$S_2 = \{1, 4\}$

$S_3 = \{1, 5\}$

$S_4 = \{2, 4, 5\}$

$S_5 = \{1, 2, 3\}$

$S_6 = \{1, 3, 4\}$

$S_7 = \{1, 4, 5\}$

$S_8 = \{1, 3, 5\}$

$S_9 = \{2, 3, 4, 5\}$

For each combination found above, find which of those combinations has the required number of green balls. These are:

$T_1 = \{1, 5\}$

$T_2 = \{1, 3, 4\}$

For each combination found above, find which of those combinations has the required number of blue balls. These are:

$U_1 = \{1, 5\}$

$U_2 = \{1, 3, 4\}$

You would need to repeat this for each color ball that you have a requirement for (here, we did this for red, green, and blue). Note the order doesn't matter. This ignores the balls of different colors that you don't have requirements for.

Answer 2

Enumerate the colors as: $$ 1{:}\; \text{red}, \;\;\; 2{:}\; \text{green}, \;\;\; 3{:}\; \text{blue}, \;\;\; 4{:}\; \text{yellow}, \;\;\; 5{:}\; \text{purple}, \;\;\; 6{:}\; \text{brown} $$ and let $a_{i,j}$ be the number of balls of color $i$ in set $j$.

Then a solution to the problem is a $5$-tuple $x=(x_1,...,x_5)$ such that \begin{align*} a_{1,1}x_1+a_{1,2}x_2+a_{1,3}x_3+a_{1,4}x_4+a_{1,5}x_5 &= 3\\ a_{2,1}x_1+a_{2,2}x_2+a_{2,3}x_3+a_{2,4}x_4+a_{2,5}x_5 &= 2\\ a_{3,1}x_1+a_{3,2}x_2+a_{3,3}x_3+a_{3,4}x_4+a_{3,5}x_5 &= 1\\ \end{align*} where each $x_i$ is $0$ or $1$.

If you just want to find one solution (if any), the problem is an instance of an integer linear programming problem.

If instead, you want find all solutions, then since the number of sets is small, you can simply test all $2^5=32$ candidates for $x$.

To reduce the search space,

• When a candidate $(x_1,...,x_5)$ fails one of the equations by having the $\text{LHS} > \text{RHS}$, don't bother trying any candidate $(x_1',...,x_5')$ for which $x_i' \ge x_i$ for all $i$.$\\[4pt]$
• When a candidate $(x_1,...,x_5)$ fails one of the equations by having the $\text{LHS} < \text{RHS}$, don't bother trying any candidate $(x_1',...,x_5')$ for which $x_i' \le x_i$ for all $i$.