How to achieve fast "vector clustering" sort?

1

I have n c-dimensional vectors that formed into a matrix A with the shape of (n, c), how can I perform a quick sort such that the vectors with low Euclidean distances are as close as possible, and the vectors with high distances are as far as possible?
For example, I have

A = [[0, 3], [0, 0], [0, 1]],

and the solution can be

A_sorted = [[0, 3], [0, 1], [0, 0]].

Explain: Because the original A has a total weighted distance sum of 3x1+1x1+2x2 = 7, and A_sorted has 2x1+1x1+3x2 = 8.
Mathematically, the goal is to maximize the total weighted distance sum.
For the 1-dimensional case, this can be achieved by torch.sort(), and my main concern is if there exists a fast implementation when c ≥ 2 with a time complexity of O(nlog(n))? :thinking:
After a long struggle, I failed. :sweat_smile: Could you please do me a favor?

2

It seems that this is as hard as Traveling Salesman Problem (I’m not sure), so sad. :cold_sweat:

3

I found that there is a similar question: Link. :sweat_smile:
Does there exists a fast PyTorch implementation that supports batch processing? (I have B instances, each instance contains N C-dimensional points, i.e. the shape of input data is [B, C, N]) :thinking:

4

I think it’s hard to directly find the optimal results, so I am pursuing a weaker solution which is fast and can find results that may not be optimal but better than random permutation or just calculating their L2 norm (distance from [0,0]) and sort, at least. :thinking: