Find vector elements that sum up to specific number

Question

ToLos Mil 2013-2-13

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/63261-find-vector-elements-that-sum-up-to-specific-number

采纳的回答： Jos (10584)

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Jos (10584) 2013-2-13

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/63261-find-vector-elements-that-sum-up-to-specific-number#answer_74913

在 MATLAB Online 中打开

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Carlos 2013-2-13

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/63261-find-vector-elements-that-sum-up-to-specific-number#answer_74871

编辑：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...

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 3

Jos (10584) 2013-2-13

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/63261-find-vector-elements-that-sum-up-to-specific-number#answer_74875

在 MATLAB Online 中打开

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

Jos (10584) 2013-2-13

FYI, I just uploaded a function NCHOOSECRIT to the File Exchange that might be useful to you.

请先登录，再进行评论。

Answer 4

ToLos Mil 2013-2-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/63261-find-vector-elements-that-sum-up-to-specific-number#answer_75153

Thank you all for your time and great solutions.

An issue remains... what if the original vector (vect) contains many elements?

2 个评论
显示无隐藏无

ChristianW 2013-2-15

在 MATLAB Online 中打开

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) 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.

请先登录，再进行评论。