Find the vector sum combination that gives the minimum vector length
4 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
tandemuse
le 23 Mar 2020
Réponse apportée : Vineeth Vijayan
le 1 Déc 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.
4 commentaires
Réponse acceptée
John D'Errico
le 23 Mar 2020
Modifié(e) : John D'Errico
le 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.
4 commentaires
Plus de réponses (1)
Vineeth Vijayan
le 1 Déc 2020
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.
- 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?
0 commentaires
Voir également
Catégories
En savoir plus sur Data Type Conversion dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!