What is the fastest way to list all positive integer vectors whose sum of elements equals K.

6 views (last 30 days)
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
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.

Sign in to comment.

Accepted Answer

Roger Stafford
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
Vu Ha
Vu Ha on 24 Jul 2014
Dear Roger Stafford,
Yes, I know this is a huge number. Then, if we add a constraint that the maximum element value of each vector is not greater than 10, the number of possible vectors will reduce a lot. So the searching process will be much faster and the memory capacity may not be exceeded. Would you please help me to solve the new problem with added constraint.
Roger Stafford
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.

Sign in to comment.

More Answers (0)

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!