How to implement such an algorithm?

Question

Say there are x number of boxes, each box contains an "inventory" of the letters A-Z, with each letter inventory being 1 or more.

Now say I need the following:

• 6 As
• 2 Bs
• 1 C

How do I get a list of all the possible combination/permutation of boxes that can provide me with the letters I need?

The algorithm needs to also produce combination of boxes to meet my requirements. For example: say Box-1 only has 4 As and Box-2 has 1 A and Box-3 has 1 A, I need the result of the algorithm to specify that the 6 As can be fulfilled across the 3 boxes.

What is the basic logic to the solution of such a problem. Are there any particular algorithms I need to be looking into for this?

EDIT 1:

Per dcp's suggestion, here's is my attempt that the PHP implementation:

$boxes = array(
 // box 1
 array(
 'A' => 6,
 'B' => 4,
 'C' => 10
 ),
 // box 2
 array(
 'A' => 8,
 'B' => 4,
 'C' => 2
 ),
 // box 3
 array(
 'A' => 1,
 'B' => 1,
 'C' => 0
 )
);
$n = count($boxes);
for ($mask = 0; $mask <= (1 << $n) - 1; $mask++)
{
 $tots = array();
 for ($i = 0; $i < $n; $i++)
 {
 if (((1 << $i) & $mask) != 0)
 {
 // this is a selected box for this mask, add the A's, B's etc. for this box to the total
 $tots[0] += $boxes[$i]['A'];
 $tots[1] += $boxes[$i]['B'];
 $tots[2] += $boxes[$i]['C'];
 }
 // check the tots array to see if it meets the letter requirements. If it does,
 // then this is a valid combination of boxes.
 }
}

• Dr. belisarius: Could you provide some background? Why do you want ALL combinations? It does not seem useful, since after listing the cases you don't have a criteria to select one. Unless it is curiosity ... or homework.
• StackOverflowNewbie: @belisarius: there doesn't have to be a criteria to select one. Perhaps the problem is solved with all combination identified. Also, why must the only 2 possible reasons why I am asking this question be "curiosity" or "homework?" Couldn't this be an actual problem I am working on?
• Dr. belisarius: Oh yes!, of course! As this is a "give and take" site, I am just asking you to share the most public part of the rationale behind your question, just to help others to recognize the kind of problem the answers you get could be applied. Valid answers are {my problem is ...}, {just curiosity}, {not your business}. The last doesn't help much, though.

Answer 1

If the number of boxes is fairly small, say 25 or less, then you could use a bitmask to brute force over all the possible box combinations:

// assume n is number of boxes, and boxes is the array of boxes
for(int mask = 0; mask <= (1<<n)-1; ++mask) {
 int tots[26];
 for(int i = 0; i < n; ++i) {
 if ( ((1<<i)&mask) != 0 ) {
 // this is a selected box for this mask, add the A's, B's etc. for this box to the total
 tots[0] += number of A's in box i
 tots[1] += number of B's in box i
 .
 .
 }
 // check the tots array to see if it meets the letter requirements. If it does, 
 // then this is a valid combination of boxes.
 }
}

• StackOverflowNewbie: @dcp: is there supposed to be a variable "boxes" in your snippet? Also, I'm not familiar with the << notation; what does it mean?
• dcp: Yes, boxes is an array of the boxes, and each array element should contain the number of a's, b's, etc. for the given box. The << notation is shift left 1 bit. (1<<n)-1 represents all the boxes being selected (so if you have 10 boxes, this number would be (2^n)-1. You can think of 1<<n and 2^n as the same, because they are :).
• asdfjklqwer: This seems like a pretty good solution to me with only one small possible problem. If there's a constraint that you have to pick up at least one letter when visiting a box, this algorithm will generate permutations which violate this. E.g. if you need just 1x A letter from x=10 boxes, this can be exactly satisfied by visiting any one of the 10 boxes since they all contain at least one instance of each letter type... but it will be 'oversatisfied' by visiting all 10 boxes (mask=1111111111), meaning that you're not picking up any letters at some of the boxes.
• StackOverflowNewbie: @dcp: i will try to translate your code into PHP, which is the language I am using. what if I were dealing with a larger number of boxes -- say in the hundreds? would this be too slow? i still need to apply some computations on each resulting combination (but they are pretty straight forward, just some basic math stuff).
• StackOverflowNewbie: @dcp: i translated your code into PHP. It never got to the point where I was supposed to check tots variable. Did I do something wrong?