10 views (last 30 days)

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

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

John D'Errico
on 17 Dec 2015

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

Start Hunting!
## 0 Comments

Sign in to comment.