Generate all possible combinations summing up to a given number

조회 수: 59 (최근 30일)
Nishant Pathak
Nishant Pathak 2021년 10월 19일
댓글: Nishant Pathak 2021년 10월 22일
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.

채택된 답변

Paul
Paul 2021년 10월 19일
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
Paul
Paul 2021년 10월 20일
Yes, on this line
[C{1:n}] = ndgrid(0:n);
C has to be either an n-element cell array or a not-yet-defined variable. So you can always do something like:
n = 2;
C = cell(1,n); % pre-allocate C
[C{1:n}] = ndgrid(0:n);
C = cell2mat(cellfun(@(x)(reshape(x,[],1)),C,'UniformOutput',false));
C(sum(C,2) == n,:)
ans = 3×2
2 0 1 1 0 2
Nishant Pathak
Nishant Pathak 2021년 10월 22일
Thanks a lot for the help.

댓글을 달려면 로그인하십시오.

추가 답변 (2개)

John D'Errico
John D'Errico 2021년 10월 20일
편집: John D'Errico 2021년 10월 20일
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
Steven Lord
Steven Lord 2021년 10월 20일
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.

댓글을 달려면 로그인하십시오.


Bruno Luong
Bruno Luong 2021년 10월 20일
편집: Bruno Luong 2021년 10월 20일
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
Bruno Luong
Bruno Luong 2021년 10월 20일
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

댓글을 달려면 로그인하십시오.

카테고리

Help CenterFile Exchange에서 Loops and Conditional Statements에 대해 자세히 알아보기

제품


릴리스

R2020b

Community Treasure Hunt

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

Start Hunting!

Translated by