Algorithm to find the 'possible' combinations of variables with constraints in Matlab?

Question

Say I have 7 items in A and 4 items in B

A=[10;40;90;130;200;260;320]
B=[100;300;500;1000]

I want to have the list of possible combinations where :

• All sub-components of A MUST be included
• sub-components of B can be added until the the SUM of all sub-componenets added is greater than 2000

Anyone has an idea how to do this in Matlab ?

My try :

X=sum(A);
y=1;
for Y=1:((length(A))-1);
   X=X+B(y);
   if(X>2000)
       disp('Following is unacceptable')    
   end
   y=y+1
end

However this code is not correct. It just adding the first element of B then adding it with the second element and so on. It isn't providing me with possible combinations.

Example :

• sum(A) + B(1) = OK
• sum(A) + B(4) = NOT OK
• sum(A) + B(1) + B(2) = OK
• sum(A) + B(2) + B(3) = OK
• etc...

I want this to be automated if values of A or B change in the future. I am not sure if this is a case of probability as well.

Answer 1

Just use nchoosek and a double for-loop to go through all possible combinations of elements in B:

SA = sum(A);
for k = 1:numel(B)
    for idx = nchoosek(1:numel(B), k)'
        B_subset = B(idx);
        if (SA + sum(B_subset) <= 2000)
            disp([A(:)', B_subset(:)'])
        end
    end
end

This prints all combinations with a sum less than (or equal to) 2000. For your example we get:

    10    40    90   130   200   260   320   100
    10    40    90   130   200   260   320   300
    10    40    90   130   200   260   320   500
    10    40    90   130   200   260   320   100   300
    10    40    90   130   200   260   320   100   500
    10    40    90   130   200   260   320   300   500
    10    40    90   130   200   260   320   100   300   500

Explanation:

The inner for-loop:
The inner for-loop uses nchoosek(1:numel(B), k), which generates all k-length combinations out of 1...length(B) (I'm using numel instead of length out of habit; in this case it has the same effect). For example, in our case B has 4 elements, so for k = 3 we get nchoosek(1:4, 3):

    1   2   3
    1   2   4
    1   3   4
    2   3   4

What we get from this is all the possible k-length combinations of indices of elements in B. In each iteration, this for-loop assigns a different combination of indices to idx. How do we convert the indices of B to real elements? We simply write B(idx).
Inside loop the combination is tested: if the total sum(A) + sum(B(idx)) is less than (or equal to) 2000, that combination is displayed.

The outer for-loop:
The outer for-loop simply iterates over all possible lengths of combinations (that is, over all possible values of k).

Hope that helps!

P.S:

Some MATLAB programming tips for the future:
1. Variable names are case-sensitive.
2. You don't need to increment the loop variable. The for loop does that automatically for you.

Answer 2

The best approach would involve some recursion, like this:

sumA=sum(A);
find_CombinationsOfB(B,sumA,[])

function ret=findCombinationsOfB(in_vals,total_sum,already_contained)

if total_sum>2000
    ret=false;
else
    for y=1:length(in_vals);
       if (~findCombinationsOfB(in_vals([1:(y-1);(y+1):length(in_vals)],total_sum+in_vals(y),[already_contained in_vals(y))
          display([already_contained in_vals])
       end
    end
    ret=true;
end

Essentially what this does is tries each combination of B. It will print any that don't add up to 2000, including the sum from A.

Step by step, here's what it does:

1. Initially, the full array of B is passed, along with the sum of A. An empty array is passed to store which elements of B have been used so far.
2. Each element added in turn to the function, and called again with a new sum, and with a value missing from the array.
3. If at any point the array sum is over 2000, it stops that chain of reasoning.

If you want to know more about how this works, print in_vals, total_sum, and already_contained in the start of the function, like this:

fprintf("in_vals=%s   total_sum=%i   already_contained=%s",mat2str(in_vals),total_sum,mat2str(already_contained));

It should show you at each iteration what is happening.