📊
scipyで二部マッチングをやってみた
こちらのサイトで紹介されている 二部マッチング ライブラリ scipy.optimize.linear_sum_assignment で遊んでみました。
コードはこちら
マトリックスをランダムで作成
二部マッチングに使うマトリックスのサイズを大きく可変にしてみました。
width = 120 # マトリックスの幅
height = 120 # マトリックスの高さ
カラムもインデックスも数値だと表示したときわかりづらいので、カラムはアルファベットにしてみました。
内包表現を使って アルファベット２文字の組み合わせ(例：a, ba, cx)まで対応してみました。
import numpy as np
import pandas as pd
from scipy.optimize import linear_sum_assignment
score = pd.DataFrame(
np.random.randint(0,30,(height,width)),
columns = [
chr(ord("`")+i//26)+chr(ord("a")+i%26) if chr(ord("`")+i//26) != '`' \
else chr(ord("a")+i%26) for i in range(width)
]
)
print(score.shape)
display(score)
(120, 120)
最大となる組み合わせ
引数 maximize を True とすることで最大となる組み合わせを算出できます。
row_index, col_index = linear_sum_assignment(score, maximize=True)
total = 0
for i, (row, col) in enumerate(zip(row_index, col_index)):
print(score.index[row], score.columns[col], ":", score.iloc[row, col], end=" ,")
if i % 5 == 4:
print()
total += score.iloc[row, col]
print("合計", total)
出力:
0 cx : 29 ,1 da : 29 ,2 av : 29 ,3 y : 29 ,4 cb : 29 ,
5 w : 29 ,6 ab : 29 ,7 h : 29 ,8 dc : 29 ,9 bo : 29 ,
(略)
115 dp : 29 ,116 cs : 28 ,117 cl : 29 ,118 bw : 29 ,119 be : 28 ,
合計 3476
最小となる組み合わせ
引数 maximize を False とすることで最小となる組み合わせを算出できます。
row_index, col_index = linear_sum_assignment(score, maximize=False)
total = 0
for i, (row, col) in enumerate(zip(row_index, col_index)):
print(score.index[row], score.columns[col], ":", score.iloc[row, col], end=" ,")
if i % 5 == 4:
print()
total += score.iloc[row, col]
print("合計", total)
出力:
0 ae : 0 ,1 bf : 0 ,2 bs : 0 ,3 o : 0 ,4 dg : 0 ,
(略)
115 co : 0 ,116 bm : 0 ,117 bu : 0 ,118 dj : 0 ,119 db : 0 ,
合計 3
120 x 120 のマトリックスからでも 1秒未満 で組み合わせを算出できるのは便利ですね。
以上になります、最後までお読みいただきありがとうございました。
参考サイト
Discussion