MATLAB Answers

Generate all possible combinations summing up to a given number

6 views (last 30 days)
Nishant Pathak
Nishant Pathak on 19 Oct 2021
Commented: Nishant Pathak on 22 Oct 2021
I could do it using nested loops manually. What I wanted is, it should automatically generate using the given value n.
Depending on n it should generate all possible combinations in which it can be summed up to n where the numbers must be filled only in n positions.
For example this program
clc
clear
n=3;
t=1;
for hh=0:n
for ii=0:n
for jj=0:n
aa=[n-hh,n-ii,n-jj];
if sum(aa(:))==n
aa1(t,:)=aa;
t=t+1;
end
end
end
end
aa1
This generates
aa1 =
3 0 0
2 1 0
2 0 1
1 2 0
1 1 1
1 0 2
0 3 0
0 2 1
0 1 2
0 0 3
But I will have to increase the loops manually if I change n. Can the numbers be generated automatically depending on n. For my use n would be usually greater than 3. Note that the numbers always sum up to n in each row.

Accepted Answer

Paul
Paul on 19 Oct 2021
n = 3;
[C{1:n}] = ndgrid(0:n);
C = cell2mat(cellfun(@(x)(reshape(x,[],1)),C,'UniformOutput',false));
C(sum(C,2) == n,:)
ans = 10×3
3 0 0 2 1 0 1 2 0 0 3 0 2 0 1 1 1 1 0 2 1 1 0 2 0 1 2 0 0 3
  3 Comments

Sign in to comment.

More Answers (2)

John D'Errico
John D'Errico on 20 Oct 2021
Edited: John D'Errico on 20 Oct 2021
These are commonly known to mathematicians as integer partitions, thus the ways we can write an integer as a sum of smaller integers. But be careful, as the number of such ways quickly becomes huge for only reasonably small N. I posted somewhere a code that computes the actual number of ways you can do this. But Wolfram Alpha does it too. (There are something like 4 trillion distinct ways to write 200 as a sum of positive integers.)
I also posted the function partitions on the file exchange, that uses a recursive scheme to compute all integer partitions of any number. (Too large and you will be sorry of course.)
partitions(3)
ans =
3 0 0
1 1 0
0 0 1
Each row is one such possibe partition. So the first row tells us that 3 = 1 + 1 + 1. In the last row, we only need one 3 to sum up to 3.
partitions(10)
ans =
10 0 0 0 0 0 0 0 0 0
8 1 0 0 0 0 0 0 0 0
6 2 0 0 0 0 0 0 0 0
4 3 0 0 0 0 0 0 0 0
2 4 0 0 0 0 0 0 0 0
0 5 0 0 0 0 0 0 0 0
7 0 1 0 0 0 0 0 0 0
5 1 1 0 0 0 0 0 0 0
3 2 1 0 0 0 0 0 0 0
1 3 1 0 0 0 0 0 0 0
4 0 2 0 0 0 0 0 0 0
2 1 2 0 0 0 0 0 0 0
0 2 2 0 0 0 0 0 0 0
1 0 3 0 0 0 0 0 0 0
6 0 0 1 0 0 0 0 0 0
4 1 0 1 0 0 0 0 0 0
2 2 0 1 0 0 0 0 0 0
0 3 0 1 0 0 0 0 0 0
3 0 1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
0 0 2 1 0 0 0 0 0 0
2 0 0 2 0 0 0 0 0 0
0 1 0 2 0 0 0 0 0 0
5 0 0 0 1 0 0 0 0 0
3 1 0 0 1 0 0 0 0 0
1 2 0 0 1 0 0 0 0 0
2 0 1 0 1 0 0 0 0 0
0 1 1 0 1 0 0 0 0 0
1 0 0 1 1 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0
4 0 0 0 0 1 0 0 0 0
2 1 0 0 0 1 0 0 0 0
0 2 0 0 0 1 0 0 0 0
1 0 1 0 0 1 0 0 0 0
0 0 0 1 0 1 0 0 0 0
3 0 0 0 0 0 1 0 0 0
1 1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 1 0 0 0
2 0 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
You can find partitions on the file exchange. Partitions has many options beyond the basic of course.
  1 Comment
Steven Lord
Steven Lord on 20 Oct 2021
FYI sequence A000041 in the On-Line Encyclopedia of Integer Sequences is the number of partitions of n. Note that this treats two partitions with the same numbers in a different order the same, so the two partitions of 2 are {2, 0} (or just plain {2}) and {1, 1}. {0, 2} is not treated as another partition.

Sign in to comment.


Bruno Luong
Bruno Luong on 20 Oct 2021
Edited: Bruno Luong on 20 Oct 2021
You can use this file exchange
n = 3;
allVL1(n,n,'==') % first parameter 3 columns, second parameter each row sum to 3
ans =
0 0 3
0 1 2
0 2 1
0 3 0
1 0 2
1 1 1
1 2 0
2 0 1
2 1 0
3 0 0
  1 Comment
Bruno Luong
Bruno Luong on 20 Oct 2021
The number of solutions for given n can be obtained
>> n=10;
>> allVL1(n,n,'==',NaN)
ans =
92378
It is in fact equal to
>> nchoosek(2*n-1,n)
ans =
92378

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by