# Find the vector sum combination that gives the minimum vector length

5 views (last 30 days)
tandemuse on 23 Mar 2020
Edited: tandemuse on 24 Mar 2020
General outline:
I have a number of vectors ,...etc as a pair of numbers such as ,...
I want to list all the possible sums of taking combinations by 2: where and and print their corresponding lengths: or at least find which sum combination of vectors gives the minimum length and the same with combinations by 3, where and .
Example:
• For example a combination by 2 let's name it to keep track of what is added would be . The length of the vector , let's call it will be .
• Or another combination would be the which gives , which is smaller than .
• Or if it was a combination by 3 we would have .
Goal:
I want the program to tell me which combination produces the smallest length and/or to print the list of all the lengths that are possible.
I hope my description is clear! :)
Thank you.

Show 1 older comment
tandemuse on 23 Mar 2020
Yes of course thank you
James Tursa on 23 Mar 2020
I assume duplicates are not allowed? E.g., A+A or A+B+B.
tandemuse on 23 Mar 2020
No (although it would be interesting to see the results of that too).

John D'Errico on 23 Mar 2020
Edited: John D'Errico on 23 Mar 2020
First, NEVER store data in multiple variables like this. Instead, LEARN TO USE ARRAYS. There is no reason why you cannot store all of your vectors of length 2 in one array, of size Nx2.
So I will assume all of your data lives in one array of that size, and use that storage method to show how to solve the problem, if possible. I'll call the array Vecs, mainly because I'm too lazy to be more creative.
Vecs = round(rand(100,2)*200 - 100);
You have integers in your vectors, so now I have random integer vectors in the range +/- 100.
That just means now you want to find the vector sum that is a combination of two rows of that array? Remember that if you have N vectors, then there will be n^2 such combinations. We can allow or disallow duplicates easily enough.
vecSumLen = sqrt((Vecs(:,1) + Vecs(:,1)').^2 + (Vecs(:,2) + Vecs(:,2)').^2);
[minlen,ind] = min(vecSumLen,[],'all','linear')
minlen =
1
ind =
5077
[rind,cind] = ind2sub(size(vecSumLen),ind)
rind =
77
cind =
51
So, if I allow replicates, the best shortest vector sum was combination of vectors 77 and 51. As it turns out, replicates were not actually a problem. But in case that is a fear, I would just add a diagonal matrix with inf on the diagonals.
vecSumLen = vecSumLen + diag(inf(size(Vecs,1),1));
Now when I apply min to the result, there is never any fear we will choose a replicate.
Note that I could also have computed the pairwise matrix using tools like pdist2, from the stats toolbox.
Your question was to also list all possible lengths. That is easy, as it is just the array vecSumLen.
Finally, be careful, as if you wanted to compute the set of 3-wise sums, there are now N^3 such possible combinations. this will get large fast. Still not that hard, but the set of all such combinations will get big. The solution will be to generate a matrix of size NxNxN, thus all such combinations.
n = size(Vecs,1);
vecSumLen = sqrt((Vecs(:,1) + Vecs(:,1)' + reshape(Vecs(:,1),[1 1 n])).^2 + (Vecs(:,2) + Vecs(:,2)' + reshape(Vecs(:,2),[1 1 n])).^2);
[minlen,ind] = min(vecSumLen,[],'all','linear');
[rind,cind,pind] = ind2sub([n,n,n],ind)
rind =
64
cind =
1
pind =
1
Vecs(64,:) + Vecs(1,:) + Vecs(1,:)
ans =
0 0
So, it turns out that if we will allow repeats, the three way pairing [64 1 1] yields exactly a vector length of 0. If we wish to kill off the repeats, we need to be more careful. Still doable though in much the same way as before.

Show 1 older comment
John D'Errico on 23 Mar 2020
NO. That your data is not integer is completely irrelevant.
What appears to be relevant is that you probably have an old release of MATLAB, something you never told us about. It usually helps to tell that information, though I do not know offhand when that option was added to min. Easy enough to learn, but surely the reason.
In an older releae, try this instead:
[minlen,ind] = min(vecSumLen(:));
tandemuse on 24 Mar 2020
I love you! This works perfectly well!
A surprising thing has happened. The same min value occurs in more than one combination.
How can I change this to see all the indeces that give the minimum length in the 3 wise sum?
%for example
vec=[1 2;0 0;0 0];
n = size(vec,1);
vecLen = sqrt((vec(:,1) + vec(:,1)' + reshape(vec(:,1),[1 1 n])).^2 + (vec(:,2) + vec(:,2)' + reshape(vec(:,2),[1 1 n])).^2);
[minlen,ind] = min(vecLen(:));
[rind,cind,pind] = ind2sub([n,n,n],ind)
in which case I only get only 2-2-2 I would also like to get the 3-2-2 etc
tandemuse on 24 Mar 2020
I played with the code a little and this turns out to be correct! :)
%for example
vec=[1 2;0 0;0 0];
n = size(vec,1);
vecLen = sqrt((vec(:,1) + vec(:,1)' + reshape(vec(:,1),[1 1 n])).^2 + (vec(:,2) + vec(:,2)' + reshape(vec(:,2),[1 1 n])).^2);
minlen=find(vecLen(:)==min(vecLen(:)));
[rind,cind,pind] = ind2sub([n,n,n],minlen)