Find vector elements that sum up to specific number

4 次查看（过去 30 天）
ToLos Mil
ToLos Mil 2013-2-13
Let us consider that we have a vector VEC.
Is ther a way to find which vector elements can be grouped so as they sum up to a given number NUM in MATLAB?
For example if VEC = [2 5 7 10] and NUM = 17
The requested algorithm should provide the answer that subvectors [2 5 10] and [7 10] sum up to given NUM.

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

采纳的回答

Jos (10584)
Jos (10584) 2013-2-13
NCHOOSECRIT is now available, so:
vect = [2 5 7 10]
num = 17
answer = nchoosecrit(vect, @(x) sum(x)==num)
See: http://www.mathworks.com/matlabcentral/fileexchange/40301

更多回答（3 个）

Carlos
Carlos 2013-2-13
编辑：Carlos 2013-2-14
I don´t know any specific Matlab command to adress your problem, however you can write an M-file to solve your problem.
A possible approach to solve your problem is to start checking all the possible combinations of two numbers within your vector. Your algorithm should start checking 2+5=17? no , so continue, 2+7=17? no, 2+10=17?,no 7+10=17?, yes, so I store 7 and 10 in a [2,1] vector(now you should continue checking the rest of the possible combinations of 2 numbers). Then you should do the same with all the possible combinations of 3 different elements, and so on...
Jos (10584)
Jos (10584) 2013-2-13
For a small number of elements in vect, you can try this vectorized approach:
vect = [2 5 7 10]
num = 17
V = nchoose(vect) ;
answer = V(cellfun(@sum,V) == num)
The function NCHOOSE can be found here:
http://www.mathworks.com/matlabcentral/fileexchange/20011
  1 个评论
Jos (10584)
Jos (10584) 2013-2-13
FYI, I just uploaded a function NCHOOSECRIT to the File Exchange that might be useful to you.

请先登录，再进行评论。

ToLos Mil
ToLos Mil 2013-2-15
Thank you all for your time and great solutions.
An issue remains... what if the original vector (vect) contains many elements?
  2 个评论
ChristianW
ChristianW 2013-2-15
You can save maybe 10-20% calculation time with vectorising Pedro's inner for-loop. But the main problem is the fast growing (n choose k). Depending on your memory, its getting hard to calculate it for length(vect) > ~30.
for n = 1:1000
C(n) = nchoosek(n,round(n/2)); %#ok<*SAGROW>
end
plot(1:n,C); set(gca,'yscale','log')
syms n; L = latex([n;n/2]);
yl = ylabel(['$' L '$'],'interpreter','latex','fontsize',13); xlabel('n')
Jos (10584)
Jos (10584) 2013-2-15
For a vector of length N, there are 2^N-1 possible subsets/subvectors. Checking them all will take some time. It depends on the problem and the elements to see whether you can discard certain subsets beforehand, e.g., by removing some elements before you loop over all subsets.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Linear Least Squares 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by