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

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

Answer 1

[John D'Errico]

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

[Lorenzo]

Hi John, thank you very much for your fast answer.

It works well, however it gives duplicates, it seems that it uses the same element more than once, listing all the combination that this element combines to the sum.

Is there the possiblity to impose just one combination for each element (unless it appears more than once), like removing them from the first array once used? Thanks again

[John D'Errico]

No. You are flat out mistaken. It does not give duplicates, unless the array of candidates has duplicates in it! In that case, what would you expect? If you tell it to use elements from the supplied array, then it will. How can it know that your set has replicates?

help unique

Just use unique first, to prevent that from happening.

[Lorenzo]

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]

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]

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