Find the vector sum combination that gives the minimum vector length

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.

[James Tursa]

Please provide a complete short example with inputs and desired output, not just a text description of what you want.

[tandemuse]

Yes of course thank you

[James Tursa]

I assume duplicates are not allowed? E.g., A+A or A+B+B.

[tandemuse]

No (although it would be interesting to see the results of that too).

Answer 1

[John D'Errico]

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.

[tandemuse]

Hello John, thank you for your answer and suggestions.

1) I get an error running the code you suggested:

Vecs = round(rand(100,2)*200 - 100);
>> vecSumLen = sqrt((Vecs(:,1) + Vecs(:,1)').^2 + (Vecs(:,2) + Vecs(:,2)').^2);
>> [minlen,ind] = min(vecSumLen,[],'all','linear')
Error using min
Dimension argument must be a positive integer scalar within indexing range.

2) My data are not integers will that be a problem? Do I have to manipulate the code somehow?

[John D'Errico]

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]

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]

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)

Answer 2

[Vineeth Vijayan]

Could you kindly extend help to my problem also?

I have two vectors A = [10 20 22 25; 2 4 5 7; 1 9 11 22] B= [5 6 12 11; 12 11 13 6; 2 12 4 11]

I need to find the min of sum of first coloumn of A. I am allowed to shift elements column wise. Whenever I shift elements in A, corresponding elements in B will also be shifted.

1. My constraint is all entries in the first column of B should be same.

Ex. A(:1) = 10 2 1 its sum is 13. But corresponding B is 5 12 2, which is not allowed.

if B = 12 12 12, A(:,1) = 22,2,4 ie. sum is 28

if B = 11 11 11, A(:,1) = 25 4 22 sum is 51.

No other combination satisfy the constraint. Hence the answer is 28.

How can i code this?

SImilarly if one change is allowed in the first coloumn of B, how to find the combinations?