CODEWITHSUNDEEP
algorithmmatlabcombinationsprobability
NLed
NLed

Reputation: 1865

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

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 :

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 :

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.

Upvotes: 4

Views: 2460

Answers (3)

Eitan T
Eitan T

Reputation: 32930

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.

Upvotes: 4

moos
moos

Reputation: 2485

Assuming B is not very long (around 10 elements), an exhaustive search through all combinations will work just fine. You can carry out this exhaustive search with a recursive function, but the code below uses a trick that's particularly concise in MATLAB: it sweeps through all combinations of the elements of B by 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

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

Upvotes: 2

PearsonArtPhoto
PearsonArtPhoto

Reputation: 39698

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.

Upvotes: 2

Related Questions