MATLAB Answers

How to take 3 elements in an array that sum to a value?

10 views (last 30 days)
Lorenzo
Lorenzo on 16 Dec 2015
Commented: Lorenzo on 21 Dec 2015
Hi everyone, I have the following problem.
I have a quite big (more than 200 elements) array "A" of numbers. I want to scan the array an take 3 numbers that sum to a certain value "k".
Once i find these 3 elements, i want to put them in another array "B" removing them from "A". Then i search for other 3 elements and continue until there are no elements that sum to "k".
At that point i change the value of "k" and begin again.
As example, if A= [1 1 2 3 4 5 5 7 8 10 11 12 14 15]; k=20, my final result will be:
B= [1 7 12 1 8 11 5 5 10 2 4 14]; A = [3 15]
I tried the following code, but it doesn't work very well, sometimes it makes mistakes with the index and removes elements from "A" without storing them in "B" (they disappear). Can you help me?
clear all
A = importdata('conn.mat');
A=A';
k=66;
D = [];
while k>50
k = k-1;
for i=1:(length(A)-2)
for l = 2:(length(A)-1)
for m = 3:length(A)
somma = (A(i)+A(l)+A(m));
if somma==(k)
D = [D A(i) A(l) A(m)];
A(m)=[];
A(i)=[];
A(l)=[];
break
end
end
end
end
end

  0 Comments

Sign in to comment.

Answers (1)

John D'Errico
John D'Errico on 16 Dec 2015
Easy, peasy. 200 is not that large of a set, although, you can easily push this too far.
As an example, I'll pick some (200) random integers from the set 1:1000 without any repeats. Then I'll find all combinations of three of those numbers that sum to 500.
A = sort(randperm(1000,200));
ind = nchoosek(1:200,3);
sum500ind = find(sum(A(ind),2) == 500);
sum500 = A(ind(sum500ind,:));
The first 10 in the list are:
sum500(1:10,:)
ans =
2 72 426
2 124 374
2 134 364
2 135 363
2 136 362
2 138 360
2 168 330
2 186 312
2 195 303
2 205 293
There are many others of course, 186 in all.
size(sum500)
ans =
186 3
As I said, you can easily overwhelm any such brute fore search.
Or, you can download my partitions code, from the file exchange, and get an answer in one single line of code. It will essentially be in the form of a 0-1 matrix here, indicating which elements of A are to be included in each sum.
p = partitions(500,A,1,3);
size(p)
ans =
186 200
If we allow elements of A to be used more than once, then there are 198 possible solutions in this case.
p = partitions(500,A,[],3);
size(p)
ans =
198 200

  5 Comments

Show 2 older comments
Lorenzo
Lorenzo on 16 Dec 2015
Hi John,
ok, the "randperm" creates unique elements, but in the array I have to use I have repetitions. In this case instead of "randperm" I have to use randi. The code is more or less like this
K = 75
A = sort(randi(100,1,200));
ind = nchoosek(1:200,3);
sum500ind = find(sum(A(ind),2) == 75);
sum500 = A(ind(sum500ind,:));
still, the ansewer in the variable "sum500" lists elements in more combinations that the number of repetitions.
In fact i have 200 numbers but the final array lists 3000 combinations!
Is there a way to solve this? Thanks for the time
John D'Errico
John D'Errico on 17 Dec 2015
If you cannot tolerate replicates, then AS I TOLD YOU TO DO, use unique FIRST on the vector of elements (A). That ensures you have no replicates. If you have no replicates, there is no issue, so I fail to see the problem.
Lorenzo
Lorenzo on 21 Dec 2015
Hi John,
no need to "scream". I may have not been totally clear, i'll try to explain better.
In my vector A i have repetitions. I have to deal with them. It represents a list of neuronal connections and sometimes two or more neurons have the same number of connections. So i want to put a combination of them in the other vector B, but only the effective combination. So if i have 2 elements that are "16" in vector A, i want 2 elements that are "16" in vector B. No more. (maybe less, if one of them remains in A).
I hope that i clarified my problem. Cheers

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!