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

Question

Vu Ha 2014-7-23

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/143103-what-is-the-fastest-way-to-list-all-positive-integer-vectors-whose-sum-of-elements-equals-k

评论： Roger Stafford 2014-7-27

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Image Analyst 2014-7-24

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.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Roger Stafford 2014-7-23

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/143103-what-is-the-fastest-way-to-list-all-positive-integer-vectors-whose-sum-of-elements-equals-k#answer_146211

在 MATLAB Online 中打开

   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 个评论
显示 5更早的评论隐藏 5更早的评论

Vu Ha 2014-7-24

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 2014-7-27

在 MATLAB Online 中打开

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.

请先登录，再进行评论。