Python 3：2つのリストから最も近い数値の「一意」の組み合わせを作りたい

Question

pythonを使って、2つのDataFrameのマッチングを行っています。
単に共通の値を基にマージするのではなく、値が近い組み合わせによってマージしたいです。
昨日投稿したところpandas.merge_asofを教えていただきましたが、一意にマージされず困っています。
例えば

df1
#       name   a
# 0        A   1
# 1        B   5
# 2        C   5
# 3        D   8
# 4        E   9

df2
#      table   a
# 0        2   2
# 1      3-1   3
# 2      3-2   3
# 3        7   7

に対して、merge_asofを使うと

pd.merge_asof(df1, df2, on='a', direction='nearest')
"""
     a  name  table
0    1     a      2
1    5     b    3-2
2    5     c    3-2
3    8     d      7
4    9     e      7
"""

と、同じ行が複数回結合されてしまいます。右側から同じ行が結合されないような、

#     a  name  table
#0    1     a      2
#1    5     b    3-1
#2    5     c    3-2
#3    8     d      7
#4    9     e    NaN

となるような組み合わせを効率よく導くにはどうしたらよいでしょうか。
いろいろ調べたのですが力及ばず…。ご教授ください。

昨日の投稿：2つのリストから最も近い数値の組み合わせを作りたい
https://teratail.com/questions/186877?nli=5cc5ee12-68c4-462b-b86e-47f40a28001e

#追記：補足
df1の値ごとに最近値を取りたいので、例えば、

df1 = pd.DataFrame({'name': ['A','B','C','D','D-2','E'],'a':[1,5,5,5,8,9]})
df2 = pd.DataFrame({'table': ['2','3-1','3-2','7'],'a':[2,3,3,7]})

のときに、

"""
   name  a  table
0     A  1     2
1     B  5   3-1
2     C  5   3-2
3     D  5     7
4   D-2  8   NaN
5     E  9   NaN
"""

ではなく

"""
   name  a  table
0     A  1     2
1     B  5   3-1
2     C  5   3-2
3     D  5   NaN
4   D-2  8     7
5     E  9   NaN
"""

となるようにしたいです。宜しくお願い致します。

Answer 1

スマートではありませんが、以下でできそうです。

import pandas as pd
import numpy as np

df1 = pd.DataFrame({'name': ['A','B','C','D','D-2','E'],'a':[1,5,5,5,8,9]})
df2 = pd.DataFrame({'table': ['2','3-1','3-2','7'],'a':[2,3,3,7]})

# df2の列値をタプル('table','a')のリストに展開
lst2 = [(r[0],r[1]) for r in df2.values]

# df2から指定値に最も近いlst2の要素位置リストを返す
def nearest(a):
    m = min(lst2, key=lambda v:(v[1]-a)*(v[1]-a))
    return [i for i,v in enumerate(lst2) if v[1] == m[1]]

used = set() # df1に割当済のlst2の要素位置

# 最近傍値に割り当て
for i,r in df1.iterrows():
    val = np.nan
    idxs = nearest(r['a'])
    while idxs:
        idx = idxs.pop(0)
        if idx not in used: # 未割当
            val = lst2[idx][0]
            used.add(idx) # 割当済を保持
            break

    df1.loc[i,'table'] = val

print(df1)
"""
  name  a table
0    A  1     2
1    B  5   3-1
2    C  5   3-2
3    D  5   NaN
4  D-2  8     7
5    E  9   NaN
"""

Comments

[takahashima]

早速回答いただきありがとうございます。
なるほどと思いましたが、df1の値ごとに最近値を取りたいので、例えば、
df1 = pd.DataFrame({'name': ['A','B','C','D','D-2','E'],'a':[1,5,5,5,8,9]})
df2 = pd.DataFrame({'table': ['2','3-1','3-2','7'],'a':[2,3,3,7]})
のときに、
name a table
0 A 1 2
1 B 5 3-1
2 C 5 3-2
3 D 5 7
4 D-2 8 NaN
5 E 9 NaN
ではなく
name a table
0 A 1 2
1 B 5 3-1
2 C 5 3-2
3 D 5 NaN
4 D-2 8 7
5 E 9 NaN
となるようにしたいです。

[can110]

最近傍値を決定する処理を見直しました。

[takahashima]

ありがとうございます。説明が難しいのですが、指定値の最近値が他の最近値で使われている場合にはその次点の値を採用できるようにしたいです。
ご教授いただいたコードですと、
df1 = pd.DataFrame({'name': ['A','B','C','D','D-2','E'],'a':[1,5,5,5,8,9]})
df2 = pd.DataFrame({'table': ['2','3-1','3-2','7','12'],'a':[2,3,3,7,12]})
のときに'E'と'12'が組み合わせられなくなってしまいます。
Σ(a-b)^2が最小となるような組み合わせで、かつdf2の全行がdf1に1度ずつマージされることを目指しています。

[can110]

おそらくその条件を加えると一意に定まらなるような気がします。
たとえば提示例にてdf1={～9,15})まであった場合、
df2の12に対応するのは9or15のどちらか決められません。

Answer 2

スマートではないですが、df1のaの値とdf2のaの値の組み合わせのパターンを列挙して、
パターンごとのΣ(a1-a2)^2を計算し、最小となる組み合わせを基にマージするというのを考えました。
組み合わせは、
df1 = pd.DataFrame({'name': ['A','B','C','D','D-2','E','E-2'],'a':[1,5,5,5,8,9,15]})
df2 = pd.DataFrame({'table': ['2','3-1','3-2','7','12'],'a':[2,3,3,7,12]})
のときには、df1の'a'7つから5つ選ぶ場合の数だけあります。（重複する値も別に考える。）
5つ選んだ値はdf2の'b'とそれぞれ小さいものから順に組み合わせます。

import pandas as pd
import numpy as np
import itertools

def merge_nearest(left,right,left_on,right_on,suffixes=['_left','_right']):
    s_left=len(left)
    s_right=len(right)
    if s_left<s_right:
        raise ValueError('len_left must be >= len_right')
    #欠損値を0で置換してsortしてreset_index
    left=left.fillna({left_on:0}).sort_values(left_on).reset_index()
    right=right.fillna({right_on:0}).sort_values(right_on).reset_index()
    l_left=left[left_on].values.tolist()
    l_right=right[right_on].values.tolist()
    #組み合わせを列挙
    c_list=list(itertools.combinations([i for i in range(s_left)],s_right))
    r=[np.nan, np.nan]
    #組み合わせごとに値の差の2乗和を計算し、最小の組み合わせとその値をrに格納
    for j in c_list:
        x=0
        for k in range(s_right):
            x+=(l_left[j[k]]-l_right[k])**2
        if np.isnan(r[1]) or r[1]>x:
            r[0]=j
            r[1]=x
    #最小となる組み合わせと右側のindexを対応させてマージ
    for m in range(s_right):
        left.at[r[0][m],'right_index']=m
    df=pd.merge(left,right,left_on='right_index',right_index=True, how='left', suffixes=suffixes)
    del df['right_index']
    return df

これを用いると、

df1 = pd.DataFrame({'name': ['A','B','C','D','D-2','E','E-2'],'a':[1,5,5,5,8,9,15]})
df2 = pd.DataFrame({'table': ['2','3-1','3-2','7','12'],'a':[2,3,3,7,12]})
df=merge_nearest(df1,df2,left_on='a',right_on='a')
df
"""
   name  a_left  table  a_right
0     A       1      2      2.0
1     B       5    3-1      3.0
2     C       5    3-2      3.0
3     D       5    NaN      NaN
4   D-2       8      7      7.0
5     E       9     12     12.0
6   E-2      15    NaN      NaN
"""

となりました。12を9か15かどちらと組み合わせるのかは一意に定まりませんが、
小さい方（.sort_values()の順）によって決まることになります。
can110さん、ご教示いただきありがとうございました。