在R语言中实现借贷双方一对一最小金额差匹配

双重循环的问题在于时间复杂度为O(n*m)，当数据集规模较大时效率极低，这里提供两种更高效的解决方案，基于Python的pandas和scipy库实现：

方法一：排序后一对一匹配 #

当两边数据集规模相同时，将借款人与贷款人分别按金额升序排序后，对应位置的配对就是差值最小的组合，这种方法时间复杂度为O(n log n + m log m)，效率很高。

import pandas as pd

# 初始化数据集
borrowers = pd.DataFrame({
    'Borrower': [1, 2, 3],
    'Amount': [1, 10, 100]
})

lenders = pd.DataFrame({
    'Lender': [4, 5, 6],
    'Amount': [95, 12, 3]
})

# 按借款/出借金额排序
borrowers_sorted = borrowers.sort_values('Amount').reset_index(drop=True)
lenders_sorted = lenders.sort_values('Amount').reset_index(drop=True)

# 匹配对应位置的贷款人
borrowers_sorted['Matched Lender'] = lenders_sorted['Lender']

# 恢复原借款人的ID顺序
result = borrowers_sorted.sort_values('Borrower').reset_index(drop=True)

print(result)

运行后输出正好符合期望结果：

方法二：匈牙利算法（通用最优匹配） #

如果数据集规模不同，或者需要严格最小化所有配对的总差值，可使用匈牙利算法（分配问题的经典解法），通过scipy库的linear_sum_assignment实现，时间复杂度为O(n³)，远优于双重循环。

from scipy.optimize import linear_sum_assignment
import numpy as np
import pandas as pd

# 初始化数据集
borrowers = pd.DataFrame({
    'Borrower': [1, 2, 3],
    'Amount': [1, 10, 100]
})

lenders = pd.DataFrame({
    'Lender': [4, 5, 6],
    'Amount': [95, 12, 3]
})

# 构建成本矩阵：所有借款人与贷款人的金额差值绝对值
cost_matrix = np.abs(borrowers['Amount'].values[:, np.newaxis] - lenders['Amount'].values)

# 执行匈牙利算法，找到最优匹配的索引
row_idx, col_idx = linear_sum_assignment(cost_matrix)

# 将匹配的贷款人ID映射到借款人数据集
borrowers['Matched Lender'] = lenders.iloc[col_idx]['Lender'].values

print(borrowers)

这种方法会自动找到总差值最小的一对一匹配，无论数据集的初始顺序如何，都能得到正确结果。

内容的提问来源于stack exchange，提问作者Ḥasan