How to find all the combinations of a vector elements whose sum is equal to a given number
27 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
Valentina Mazzoni
am 8 Mai 2020
Kommentiert: Rami Matar
am 5 Okt. 2020
Hi all,
I' ve got this vector made of 24 elements:
P = [250 500 500 1250 2500 5000 5000 15000 15000 15000 15000 8166 8926 9796 10800 11967 13333 14948 16875 16875 19200 22041 22041 25562 ]
and I've got a target value "n" to reach by combining a certain number of elements of P and adding them together:
n=3000 (it changes all the times because it's an input given by the user)
Every single element of the vector has to be taken just one time in the sum.
Do you have any ideas of how I can do it? Thanks.
0 Kommentare
Akzeptierte Antwort
Stephen23
am 8 Mai 2020
Bearbeitet: Stephen23
am 8 Mai 2020
A simple recursive nested function, with short-circuiting for combinations whose sums are greater than N (this makes the whole thing viable for small values of N and give results as quickly as possible):
function C = temp4(N)
P = [250,500,500,1250,2500,5000,5000,15000,15000,15000,15000 8166,8926,9796,10800 11967,13333,14948,16875,16875,19200,22041,22041,25562];
C = {};
for ii = 1:numel(P)
nestfun(P(ii),P(ii+1:end))
end
function nestfun(t,V)
if sum(t)<N
for jj = 1:numel(V)
nestfun([t,V(jj)],V(jj+1:end))
end
elseif sum(t)==N
C{end+1} = t;
end
end
end
Tested (the repeated vectors are due to the repeated values in P):
>> temp4(3000)
ans = {
[500 2500]
[500 2500]}
>> temp4(30000) % a much more interesting example
ans = {
[250 500 500 1250 2500 5000 5000 15000]
[250 500 500 1250 2500 5000 5000 15000]
[250 500 500 1250 2500 5000 5000 15000]
[250 500 500 1250 2500 5000 5000 15000]
[15000 15000]
[15000 15000]
[15000 15000]
[15000 15000]
[15000 15000]
[15000 15000]
[10800 19200]}
Note that if N is large then you can expect to be waiting for some time... e.g. given all 620,448,401,733,239,000,000,000 combinations at a rate of 1 million checks per second, you would have to wait around
>> yrs = 620448401733239000000000/1e6/60/60/24/365 % years
yrs = 19674289755.62021
>> num2words(yrs,'sigfig',1,'type','money','unit','Year|')
ans = twenty billion years
10 Kommentare
Bruno Luong
am 4 Okt. 2020
I guess you can replace P with Pr like this
>> P=1:5
P =
1 2 3 4 5
>> s=5
s =
5
>> Pr=repelem(P,floor(s./P))
Pr =
1 1 1 1 1 2 2 3 4 5
Then use Stephen's algorithm on Pr.
Weitere Antworten (0)
Siehe auch
Kategorien
Mehr zu Resizing and Reshaping Matrices finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!