Algorithm for finding "possible" combinations of variable constraints in Matlab?

Question

Say I have 7 elements in and 4 elements in B

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

I want to have a list of possible combinations , where:

• All subcomponents A MUST be included
• subcomponents B can be added up to , SUM of all added additional components more than 2000

Does anyone have an idea how to do this in Matlab?

My attempt:

 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 incorrect. It simply adds the first element of B, and then adds it with the second element, and so on. This does not give me 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 the values ​​of A or B change in the future. I am not sure if this is a case of probability.

Answer 1

Just use nchoosek and 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 displays all combinations with an amount 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:

Internal for -loop :
The inner for -loop uses nchoosek(1:numel(B), k) , which generates all k-length combinations from 1 ... length (B) (I use numel instead of length out of habit, in which 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 

From this we get all possible combinations of k-length indices of elements from B At each iteration, this for -loop assigns a different idx index combination. How do we convert indices B to real elements? We just write B(idx) .
The combination is checked inside the loop: if the total sum(A) + sum(B(idx)) less (or equal to 2000), this combination is displayed.

External for -loop :
The external for -loop simply iterates over all possible combination lengths (i.e., over all possible k values).

Hope this helps!

PS:

Some MATLAB programming tips for the future:
1. Variable names are case-sensitive.
2. You do not need to increase the loop variable. The for loop does this automatically for you.

Answer 2

Assuming B is not very long (about 10 items), an exhaustive search on all combinations will work fine. You can do this exhaustive search using a recursive function, but the code below uses a trick that is especially concise in MATLAB: it scans all combinations of B elements, representing each combination as a binary bit string.

 % examine each of 2^length(B) combinations for i=0:2^length(B)-1 % converts the binary string into an array of 0 and 1 used to select elements in B combo = dec2bin(i, length(B))-'0'; % print the combination of elements if their sum is large if combo * B + sum(A) > 2000 disp(find(combo)); end end 

Combinations of 2 ^ lengths (B) are possible. This in turn checks them, representing the combination as a binary string of length (B) length and evaluating the sum of these elements (with the dot product between the bit string and B).

Answer 3

The best approach involves some recursion, for example:

 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 

In fact, this is an attempt of each combination B. It will print any that do not contain up to 2000, including the amount from A.

Step by step, here is what he does:

• First, the full array from B is transferred along with the sum of A. An empty array is transferred to store which elements from B have been used so far.
• Each element is added in turn to the function and is called again with a new sum and with a value not in the array.
• If at any point the sum of the array exceeds 2000, it stops the chain of reasoning.

If you want to know more about how this works, type in_vals, total_sum and already_ at the beginning of the function, for example:

 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 going on.