Как эффективно отсортировать вектор, чтобы иметь минимальное расстояние до другого вектора?

Question

У меня есть два вектора (v1, v2). Значения в векторе v2 необходимо отсортировать, чтобы каждое из них можно было идентифицировать с элементом в v1. Значения в v1 и v2 немного отличаются, но могут быть изменены. В конце мне нужно сделать это несколько раз, так как мне нужно отсортировать следующий v3 по отсортированному v2 и т. Д.

Я думал о рассмотрении различных перестановок v2 для каждого возможного упорядочения значений в v2. Минимальная сумма отличий от v1 должна быть той сортировкой, которую я хочу получить. Это работает в принципе, но масштабируется ужасно, когда v1 и v2 становятся больше.

Этот код показывает порядок для пары v1, v2.

import numpy as np
import itertools

def sort(v1,v2):

    arr_permutations = np.array(list(itertools.permutations(v2)))

    sum_diff = np.sum(np.abs(arr_permutations - v1), axis=1)

    best_permut = arr_permutations[np.argmin(sum_diff)]

    return best_permut 

v1 = np.array([-0.99418 -0.106364j, -1.005974-0.099054j,
 -0.991923-0.107482j, -0.990868-0.107976j, -0.990558-0.108118j,
 -0.898555+0.035351j])

v2 = np.array([-1.0052  -0.10133j,  -0.993598-0.108516j,
  0.991379-0.109617j, -0.990341-0.110104j, -0.990036-0.110244j, 
 -0.898624+0.032346j])

sort(v1,v2)

Out:  np.array([-0.993598-0.108516j, -1.0052  -0.10133j, 
                -0.990341-0.110104j, -0.990036-0.110244j, 
                 0.991379-0.109617j, -0.898624+0.032346j])

В этом случае правильным порядком является замена v2 [0] и v2 [1] в этом конкретном случае. Поскольку все значения, которые принадлежат друг другу, немного меняются, недостаточно просто посмотреть на одно значение и найти отдельную позицию, ближайшую к значению в v1.

Редактировать: я изменил пример и добавил, каким будет вывод функции.

Редактировать 2: добавлена ​​пропущенная запятая в массиве numpy

Answer 1

Вот моя попытка:

import numpy as np
from scipy import optimize

def match(v1, v2, dist):
    assert v1.ndim == v2.ndim == 1
    assert v1.shape[0] == v2.shape[0]
    n = v1.shape[0]
    t = np.dtype(dist(v1[0], v2[0]))
    dist_matrix = np.fromiter((dist(x1, x2) for x1 in v1 for x2 in v2),
                              dtype=t, count=n*n).reshape(n, n)
    row_ind, col_ind = optimize.linear_sum_assignment(dist_matrix)
    return v2[col_ind]

v1 = np.array([-0.99418 -0.106364j, -1.005974-0.099054j, -0.991923-0.107482j,
               -0.990868-0.107976j, -0.990558-0.108118j, -0.898555+0.035351j])
v2 = np.array([-1.0052  -0.10133j,  -0.993598-0.108516j,  0.991379-0.109617j,
               -0.990341-0.110104j, -0.990036-0.110244j, -0.898624+0.032346j])

v2_matched = match(v1, v2, lambda x1, x2: abs(x1 - x2))
print(repr(v2_matched))
# =>
# array([-0.993598-0.108516j, -1.0052  -0.10133j , -0.990341-0.110104j,
#        -0.990036-0.110244j,  0.991379-0.109617j, -0.898624+0.032346j])

Вывод такой же, как у вашего sort().

Как видите, вы можете подключить другую лямбду или функцию для расстояния.

Я не эксперт по numpy, может быть ярлык для вычисления матрицы расстояний dist_matrix.

Спасибо @Jonas за определение « проблемы с назначением ».