Эффективная пара и выберите

Question

Я стараюсь более эффективно выбрать лучшую комбинацию пар без повторов. Существует два набора из 3 значений, значения, которые наиболее похожи, должны быть объединены, так как из одной пары создается значение, с которым было сопоставлено, больше не нужно выбирать.

Например - A1 - 4,3 B1 - 4,4 A2 - 0,5 B2 - 2,3 A3 - 2,4 B3 - 1,0

Таким образом, наиболее похожими являются значения: A1B1, A2B3, A3B2. Первая сделанная пара, и любые другие комбинации пар могут быть проигнорированы при выборе каждой пары.

Пример - A1B1 0,1, A1B2 1,4, A1B3 2,0, A2B1 3,9, A2B2 1,8, A2B3 0,5, A3B1 2.0, A3B2 0.1, A3B3 1.4

Приведенный выше пример является несколько упрощенной версией моей проблемы, поскольку у меня есть 5 групп с двумя разными значениями, которые должны быть наиболее похожими, и у меня есть около 200 000 из этих групп для объединения.

В настоящее время у меня есть код python, аналогичный приведенному ниже, который сортирует каждый фрейм данных после создания всех возможных комбинаций, но он очень медленный:

df1 = pd.DataFrame([['s','group_x',1,4.3,10],['s','group_x',2,0.5,8],['s','group_x',3,2.4,43],['t','group_x',1,5.9,13],['t','group_x',2,2.0,20],['t','group_x',3,1.3,38]],columns=['info','type','group','x','y'])
df2 = pd.DataFrame([['s','group_y',1,4.4,12],['s','group_y',2,2.3,33],['s','group_y',3,1.0,10],['t','group_y',1,2.3,21],['t','group_y',2,5.0,15],['t','group_y',3,0.9,42]],columns=['info','type','group','x','y'])

df = pd.merge(df1, df2, on=['info'], sort=False)
df['x'] = abs(df['x_x'] - df['x_y'])
df['y'] = abs(df['y_x'] - df['y_y'])

best = pd.DataFrame(columns=list(df))
# for each set of combinations
for i in range(0,len(df), 8):
    # sort set by values to get closest values at top
    sett = df.loc[i:i+8].sort_values(by=['group_x','x','y']).reset_index(drop=True)
    # for each combination
    for j in range(1,3):
        # select top pair and add to best df
        best = best.append(sett.loc[0], ignore_index=True, sort=False)
        # remove best group_2 used and best group_1 already paired
        sett = sett[sett['group_y'] != sett['group_y'][0]]
        sett = sett[sett['group_x'] != j].reset_index(drop=True)

В целом просто пытаюсь выбрать лучшая пара из множества вариантов без повторов.