What is the fastest way to list all positive integer vectors whose sum of elements equals K.
6 views (last 30 days)
Show older comments
For example I want to list all row vectors (1,5) whose elements are positive integers and sum of elements equals to 20. I am looking for a fast way which not use the loop-for for each elements. Please help.
1 Comment
Image Analyst
on 24 Jul 2014
Vu Ha posted this virtually identical question in another post for some reason, so I moved it here and deleted that one:
For example I want to list all row vectors (1,30) whose elements are positive integers and sum of elements equals to 90, and the maximum element is not greater than 10. I am looking for a fast way which not use the loop-for for each elements. Please help.
Accepted Answer
Roger Stafford
on 23 Jul 2014
K = 20; % The required sum
n = 5; % The number of elements in the rows
c = nchoosek(2:K,n-1);
m = size(c,1);
A = zeros(m,n);
for ix = 1:m
A(ix,:) = diff([1,c(ix,:),K+1]);
end
The rows of A will have the vectors you seek. In your example there will be 19!/4!/15! = 3876 such row vectors.
Note: I don't think this code works for the trivial case of n = 1.
7 Comments
Roger Stafford
on 27 Jul 2014
Vu Ha, here is a function you can use to compute the total number of possible sequences of 'n' positive integers whose sum is 's' with none of them in excess of 'u'. It is very fast.
function c = count(s,n,u);
x = zeros(s+u+1,n+1);
x(u+1,1) = 1;
for k = 2:n+1
t = cumsum(x(:,k-1));
x(u+2:s+u+1,k) = t(u+1:s+u)-t(1:s);
end
c = x(s+u+1,n+1);
return
However, it does not generate such a list of sequences, but only gives the count of how many are possible. Such a generation can be done but it uses a rather inefficient 'eval' method. I don't know of any faster way of accomplishing this latter task.
As you can quickly determine using the above function 'count', your attempt to use s = 90 is not very practical. With count(90,30,10) you get c = 1.346533650172073e+23 (which is roughly the total number of molecules in four grams of water!) With u as low as 4 you get count(90,30,4) = 3.717608331097920e+15 which is still a monstrous number. To get something below a million, I would recommend something like count(30,10,5) which gives 856945. Even that would probably take quite some time to generate a full list of all possible sequences.
More Answers (0)
See Also
Categories
Find more on Loops and Conditional Statements in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!