Combination of possible values in an array with multiple constraints in Matlab?

Question

I have an array B of :

B=[1 2 3; 10 20 30 ; 100 200 300 ; 1000 2000 3000]

such that

B =

           1           2           3
          10          20          30
         100         200         300
        1000        2000        3000

I am using the following code to find the possible combination between these variables that are below a certain value (a constraint) -- 2000 in this case :

A=[123; 323; 12 ; 421]
SA=sum(A)
V=cell(length(B),1);
n=1;
for k = 1:length(B)
    for idx = nchoosek(1:length(B), k)'
        B_subset = B(idx);
        if (SA + sum(B_subset) <= 2000)
            V(n)={B_subset(:)}; %store them in a cell
            n=n+1;
        end
    end
end

However I failed to combine them the way I want below.

Objective :

Find the possible combinations from B to be added with SA so that their sum is less than 2000 ?

Constraint 1 :

Only one value from each row in array B can be used at once.

For example, this is NOT acceptable : [1 2 20] [2 20 30]
This is the correct one : [1 20 100] [3 200 3000]

Constraint 2 : - The answers should be stored in the cell V in only one column (as initialised in the code above).

The cell should have an output similar to the one I'm currently having :

V = 

    [       100]
    [       300]
    [       200]
    [2x1 double]
    [2x1 double]
    [2x1 double]
    [3x1 double]

are the contents of V OK? Do you just need output formatting? — Dedek Mraz
– Dedek Mraz, Commented Mar 7, 2013 at 18:26
The V looks suspiciously familiar :) Will update the answer. — Dedek Mraz
– Dedek Mraz, Commented Mar 7, 2013 at 18:39

Dedek Mraz · Accepted Answer · 2013-03-07 22:02:53Z

1

Changed your code just a bit and added a test below - if V is unchanged -> there were no combinations -> display that. Edited to allow saving it into cell array V and simultaneously constructing a string for printing.

This code considers every combination of three elements from B, where each element is from a different column.

V=cell(length(B),1);
A=[123; 323; 12 ; 421];
SA=sum(A);
S = 'possible combinations :';
n = 1
for ii=1:4
    for jj=1:4
        if jj == ii
            continue
        end
        for kk=1:4
            if or(kk == jj,kk == ii)
                continue
            end
            B_subset = [B(ii,1), B(jj,2), B(kk,3)];
            if (SA + sum(B_subset) <= 2000)
                S = [S, ' ', mat2str(B_subset)];
                V{n} = B_subset;
                n += 1;
            end
        end
    end
end

if V == 'possible combinations :'
    disp('No possible combinations found')
else
    disp(S)
end

EDIT: adding answer to the new part of the question. In the inner-most loop the different combinations of included rows are calculated.

V = {}
for ii=1:3
    for jj=1:3
        for kk=1:3
            for ll = 1:3
                rows = [ii, jj, kk, ll]
                if isequal(rows, unique(rows))
                    % loop for turning off individual elements
                    result = [B(1,ii), B(2,jj), B(3,kk), B(4,ll)]
                    for mm = 0:1:15
                        % make a binary string - will loop through all combinations of zeros and ones
                        str1 = dec2bin(mm,4)
                        mask = zeros(1,4)
                        for nn = 1:4 % make a numeric vector
                            mask(nn) = str2num(str1(nn))
                        end
                        masked_result = mask.*result
                        V = [V {masked_result}]
                    end
                end
            end
        end
    end
end

edited Mar 7, 2013 at 22:02

answered Mar 7, 2013 at 18:37

Dedek Mraz

8147 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

13 Comments

NLed Over a year ago

The code still uses values from the same row, such as 100 200 30 or 10 200 30

Dedek Mraz Over a year ago

You said one value from each column: this is done with the three loops. Then you said only one value per row - which is done with continues. It can't do 100 200 30 because jj and ii would be the same and it would continue before checking for answer. V has old values in it, because it wasn't initialized again. I've updated the answer, also changing looping to 4 for the whole B.

Dedek Mraz Over a year ago

@NLed: I don't understand what you want. Every viable answer is a 1x3 matrix. Why are there 4 elements? Also, do you want to also print answers that exceed 2000 or even combinations that share a row or column?

Dedek Mraz Over a year ago

Hm. I think I know what you want, but this is a large number of results - seems like over 60. Don't quite know how to do it. Still thinking :)

Dedek Mraz Over a year ago

Look man, I gave it my best. Your request are strange and hard to comprehend. Plus I don't think this question is going to help anyone else - so we are littering here. Please try to do something by yourself and especially try to understand what the code does. Matlab has an excellent framework for running scripts and checking values after each line of code. I really suggest you try it. You can run scripts right from Matlab's text editor.

|

Eitan T · Accepted Answer · 2013-03-07 19:34:12Z

1

Here, this fix should do the trick:

SA = sum(A);
V = cell(numel(B), 1);                  % // Changed 'length' to 'numel'
n = 1;
for k = 1:size(B, 1)                    % // Changed 'length' to 'size'
    for idx = nchoosek(1:numel(B), k)'  %'// Changed 'length' to 'numel'

        %// Ignore the combination if there are two elements from the same row
        rows = mod(idx, size(B, 1));
        if ~isequal(rows, unique(rows))
            continue
        end

        B_subset = B(idx);
        if (SA + sum(B_subset) <= 2000)
            V(n) = {B_subset(:)};
            n = n + 1;
        end
    end
end

Perhaps it's not the most efficient solution there is, but it's short and it works.

answered Mar 7, 2013 at 19:34

Eitan T

33k14 gold badges77 silver badges111 bronze badges

5 Comments

NLed Over a year ago

example, what does ~isequal mean ? and how is this code going over different rows/columns before checking if they are viable combinations ?

Dedek Mraz Over a year ago

@NLed numel means number of elements - in this case it is 4x3=12. ~ is negation in matlab, so this ~isequal means if rows is not equal to unique(rows) - that happens when there are duplicated elements in rows

NLed Over a year ago

@EitanT I have used your code for another question, maybe it will interest you. stackoverflow.com/questions/15284999/…

Eitan T Over a year ago

@NLed Did this code resolve the problem described in this question?

NLed Over a year ago

@EitanT Yes I am actually using your code now with just minor tweaks, which I really appreciate very much. If you are interested to see how it looks like then let me know.

Collectives™ on Stack Overflow

Combination of possible values in an array with multiple constraints in Matlab?

2 Answers 2

13 Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

13 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related