CODEWITHSUNDEEP
algorithmmatlab
giulio
giulio

Reputation: 659

Sum over all subsets in matlab

Given a number 'c' and a list of numbers 'numbers', I am trying to generate all the sums I can have of c and any subset in numbers. eg. (1,[2,4,8]), I should generate (note that we should always have c in a sum) [1,3,5,9,7,11,13,15]

I wrote the following code, but not all sums appear. What is wrong?

function result = allsums(c, numbers)
    if isempty(numbers)
        result = [];
    else
        [nr n_numbers] = size(numbers);
        for i = 1:n_numbers
            result = cat(2, c+numbers(i), allsums(c, cat(2,numbers(1:i-1),numbers(i+1:end))));
        end
    end

result = cat(2, result, c+sum(numbers,2));
end

Upvotes: 2

Views: 1031

Answers (3)

Luis Mendo
Luis Mendo

Reputation: 112769

How about a one-line solution?

c = 1; %// number 
S = [2 4 8]; %// set

result = unique(c+S*(dec2bin(0:2^numel(S)-1).'-'0'));

Explanation: The key here is dec2bin(0:2^numel(S)-1).'-'0', which produces a 0-1 pattern indicating which elements of the set S get added. In the example this is

 0     0     0     0     1     1     1     1
 0     0     1     1     0     0     1     1
 0     1     0     1     0     1     0     1

Each column corresponds to a different subset of S. Matrix multiplication by S then gives the sum for each subset.

Upvotes: 2

Divakar
Divakar

Reputation: 221714

This could be one approach -

%// Input array and scalar
numbers = [2,4,8] 
c = 1;

%// Generate all sums for all combinations with nchoosek; then add up with c
combsums = arrayfun(@(n) sum(nchoosek(numbers,n),2),1:numel(numbers),'Uni',0)
result = [c ; c+vertcat(combsums{:})]

Code run -

result =
     1
     3
     5
     9
     7
    11
    13
    15

Upvotes: 3

scmg
scmg

Reputation: 1894

Wrong in the line:

result = cat(2, sums, c+sum(numbers,2));

Because you recalled function sums without input arguments, while you wrote the function with 2 input arguments.

UPDATE:

if length(numbers) less than 15 (http://www.mathworks.com/help/matlab/ref/nchoosek.html), you can try nchoosek like this:

function result = sums(c, numbers)
  result = [];
  if ~isempty(numbers)
    [nr n_numbers] = size(numbers);
    result = c;
    for i = 1:n_numbers
      combi = nchoosek(numbers, i);
      for j = 1:size(combi, 1)
        result(end+1) = c + sum(combi(j,:));
      end
    end
  end
  result = unique(result);
end

p/s: just a very quick example, you can try to optimize the code, i'm not sure if using recursion like yours is better or using Matlab's built-in functions is better ...

Upvotes: 2

Related Questions