How to take 3 elements in an array that sum to a value?
15 ビュー (過去 30 日間)
古いコメントを表示
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 件のコメント
回答 (1 件)
John D'Errico
2015 年 12 月 16 日
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 件のコメント
John D'Errico
2015 年 12 月 17 日
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.
参考
カテゴリ
Help Center および File Exchange で Matrix Indexing についてさらに検索
製品
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!