CODEWITHSUNDEEP
matlab
newbie2015
newbie2015

Reputation: 581

All possible combinations such that sum of all numbers is a fixed number

I need to find all possible combinations of numbers 1:8 such that sum of all elements is equal to 8 The combinations need to be arranged in an ascending order.

Eg

1 7

2 2 4

1 3 5

1 2 2 3

1 1 1 1 1 1 1 1

A number can repeat itself. But a combination must not.. i.e 1 2 2 3 and 2 1 2 3 I need the the solution in ascending order So there will be only one possibility of every combination

I tried a few codes online suggested on Find vector elements that sum up to specific number in MATLAB

   VEC = [1:8];
      NUM = 8;
      n = length(VEC);
      finans = zeros(2^n-1,NUM);
      for i = 1:(2^n - 1)
        ndx = dec2bin(i,n) == '1';
        if sum(VEC(ndx)) == NUM
        l = length(VEC(ndx));
        VEC(ndx)
        end
      end

but they dont include the possibilities where the numbers repeat.

Upvotes: 4

Views: 2053

Answers (3)

krisdestruction
krisdestruction

Reputation: 1960

EDIT: Look at my second more efficient answer!

The Naive approach! Where the cartprod.m function can be found here.

% Create all permutations
p(1:8) = {0:8};
M = fliplr( cartprod( p{:} ) );

% Check sums
r = sum( M, 2 ) == 8;
M = M(sum( M, 2 ) == 8,:);   % Solution here

There are definitely more efficient solutions than this but if you just need a quick and dirty solution for small permutations, this will work. Please note that this made Matlab take 3.5 GB of RAM to temporarily store the permutations.

Upvotes: 2

krisdestruction
krisdestruction

Reputation: 1960

I found a better approach through recursion and it's more elegant (I like elegant) and faster than my previous attempt (0.00399705213 seconds on my computer).

EDIT: You will need my custom function stretchmat.m that stretches a vector to fit the size of another matrix. Kinda like repmat but stretching the first parameter (see help for details). Very useful!

script.m

% Define funciton to prepend a cell x with a variable i
cellprepend = @(x,i) {[i x]};

% Execute and time function
tic;
a = allcomb(cellprepend,1,8);   % Solution in a
toc;

allcomb.m

function a = allcomb( cellprepend, m, n )
    % Add entire block as a combination
    a{1} = n;

    % Exit recursion if block size 1
    if n == 1
        return;
    end

    % Recurse cutting blocks at different segments
    for i = m:n/2
        b = allcomb(cellprepend,i,n-i);
        a = [a cellfun( cellprepend, b, num2cell( stretchmat( i, b ) ) )];
    end
end

So the idea is simple, for solutions that add to 8 is exhaustive. If you look for only valid answers, you can do a depth first search by breaking up the problem into 2 blocks. This can be written recursively as I did above and is kinda similar to Merge Sort. The allcomb call takes the block size (n) and finds all the ways of breaking it up into smaller pieces.

We want non-zero pieces so we loop it from 1:n-1. It then prepends the first block to all the combinations of the second block. By only doing all comb on one of the blocks, we can ensure that all solutions are unique.

As for the sorting, I'm not quite sure what you mean by ascending. From what I see, you appear to be sorting from the last number in ascending order. Can you confirm? Any sort can be appended to the end of script.m.

EDIT 2/3 Notes

  • For the permutatively unique case, the code can be found here
  • Thanks to @Simon for helping me QA the code multiple times

Upvotes: 2

Simon
Simon

Reputation: 5412

First save all combinations with repetitions in a cell array. In order to do that, just use nmultichoosek.

v = 1 : 8;
combs = cell(length(v),0);
for i = v
    combs{i} = nmultichoosek(v,i);
end

In this way, each element of combs contains a matrix where each row is a combination. For instance, the i-th row of combs{4} is a combination of four numbers.

Now you need to check the sum. In order to do that to all the combinations, use cellfun

sums = cellfun(@(x)sum(x,2),combs,'UniformOutput',false);

sums contains the vectors with the sum of all combinations. For instance, sums{4} has the sum of the number in combination combs{4}.

The next step is check for the fixed sum.

fixed_sum = 10;
indices = cellfun(@(x)x==fixed_sum,sums,'UniformOutput',false);

indices contains arrays of logical values, telling if the combination satisfies the fixed sum. For instance, indices{4}(1) tells you if the first combination with 4 numbers sums to fixed_sum.

Finally, retrieve all valid combinations in a new cell array, sorting them at the same time.

valid_combs = cell(length(v),0);
for i = v
    idx = indices{i};
    c = combs{i};
    valid_combs{i} = sortrows(c(idx,:));
end

valid_combs is a cell similar to combs, but with only combinations that sum up to your desired value, and sorted by the number of numbers used: valid_combs{1} has all valid combinations with 1 number, valid_combs{2} with 2 numbers, and so on. Also, thanks to sortrows, combinations with the same amount of numbers are also sorted. For instance, if fixed_sum = 10 then valid_combs{8} is

 1     1     1     1     1     1     1     3
 1     1     1     1     1     1     2     2

This code is quite efficient, on my very old laptop I am able to run it in 0.016947 seconds.

Upvotes: 0

Related Questions