2

Let us consider that we have a vector VEC.

Is ther a way to find which vector elements can be grouped so as they sum up to a given number NUM in MATLAB?

For example if VEC = [2 5 7 10] and NUM = 17

The requested algorithm should provide the answer that subvectors [2 5 10] and [7 10] sum up to given NUM.

bla
  • 25,846
  • 10
  • 70
  • 101
ToLos Mil
  • 63
  • 1
  • 6
  • Are you looking for a solution for small vectors, or does it also need to work for long vectors? (thousands of elements?) – Dennis Jaheruddin Feb 13 '13 at 14:49
  • It would be helpful if the algorithm worked for vectors that contain number of elements from 10 to 50. – ToLos Mil Feb 15 '13 at 09:15
  • In that case you may want to reconsider your needs. You may have already expected this, but for a vector of length 50 the number of results can exceed 10^14. Perhaps you only need a few results? – Dennis Jaheruddin Feb 15 '13 at 09:44
  • I expexted it really, but I wonder if an algorithm exists that can provide a solution possibly by using heuristic rules, thus avoiding to explore the whole space of possible solutions. – ToLos Mil Feb 15 '13 at 10:10
  • Assuming `vec = ones(50)` and `num = 25` which solutions would you like to see? – Dennis Jaheruddin Feb 15 '13 at 10:19

3 Answers3

3

Here is a way to solve this using conbntns, a function from the Mapping Toolbox that retrieves all possible combinations of set of values (if you don't have this toolbox, you can use combinator from the FEX). So, for vector A, for example, we'll find all possible combination of a given length (1 to the length of A) then sum them and see which is equal to NUM=17:

NUM=17;
A=[2 5 7 10];
for ii=1:numel(A)
    B=combntns(A,ii);
    C=sum(B,2);
    D=find(C==NUM);
    if ~isempty(D)
        B(D,:)
    end
end

ans =
     7    10
ans =
     2     5    10

Of course you can store B(D,:) output into a cell array or whatever for future use...

bla
  • 25,846
  • 10
  • 70
  • 101
3

Here's another way to do it without any toolboxes or third party functions. It steps through all possible combinations of values in VEC and tests if the sum equals NUM.

VEC = [2 5 7 10]
NUM = 17;
n = length(VEC);
for i = 1:(2^n - 1)
    ndx = dec2bin(i,n) == '1';
    if sum(VEC(ndx)) == NUM
        VEC(ndx)
    end
end

ans =
     7    10
ans =
     2     5    10

This is similar to natan's answer, but without using conbntns.

Community
  • 1
  • 1
shoelzer
  • 10,648
  • 2
  • 28
  • 49
  • please [don't use `i` as a variable](http://stackoverflow.com/questions/14790740/using-i-and-j-as-variables-in-matlab) in matlab – Shai Feb 13 '13 at 16:46
  • I do it all the time. I do not use `i` for imaginary numbers. [For speed and improved robustness, you can replace complex i and j by 1i.](http://www.mathworks.com/help/matlab/ref/i.html) – shoelzer Feb 13 '13 at 18:25
  • @Shai I posted my argument as a response to the question you linked. – shoelzer Feb 13 '13 at 19:13
2

If I'm not mistaken this problem is NP-hard.
But an interesting approach might be using bintprog:

n = numel( VEC );
x0 = zeros( 1, n ); % one possible init guess
x = bintprog( zeros( n, 1 ), ...  % objective function meaningless, we look for feasibility
              [], [], ... % no inequality constraints
              VEC(:)', NUM, ... %' we want the sum of selected elements to equal NUM
              x0 ); % changing init x0 might result with different solutions
find( x )

the binary vector x (the solution of the optimization in bintprog) selects the relevant elements that sum to NUM

Shai
  • 111,146
  • 38
  • 238
  • 371
  • Very nice approach indeed, but as i understand it, it can not provide all possible solutions (for example in the given example there are two possible solutions, i.e. [7 10] and [2 5 10]). Am i wrong? – ToLos Mil Feb 15 '13 at 09:18
  • @ApostolosMilioudis - you are correct. `bintprog` searches for a single solution only. However, since the problem is NP complete, this might find a solution faster than O(2^n)... – Shai Feb 17 '13 at 06:13