Generate all possible combinations summing up to a given number
44 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
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.
Réponse acceptée
Paul
le 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,:)
3 commentaires
Paul
le 20 Oct 2021
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,:)
Plus de réponses (2)
John D'Errico
le 20 Oct 2021
Modifié(e) : John D'Errico
le 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 commentaire
Steven Lord
le 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.
Bruno Luong
le 20 Oct 2021
Modifié(e) : Bruno Luong
le 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 commentaire
Bruno Luong
le 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
Voir également
Catégories
En savoir plus sur Loops and Conditional Statements dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!