Generate all possible combinations summing up to a given number

63 次查看（过去 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
Ran in:
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 个评论
显示 1更早的评论
Paul
Paul 2021-10-20
Ran in:
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

请先登录，再进行评论。

更多回答（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.
https://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer?s_tid=srchtitle
  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
https://www.mathworks.com/matlabcentral/fileexchange/17818-all-permutations-of-integers-with-sum-criteria
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 Center 和 File 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