📊

scipyで二部マッチングをやってみた

2022/02/11に公開

こちらのサイトで紹介されている 二部マッチング ライブラリ scipy.optimize.linear_sum_assignment で遊んでみました。

https://myenigma.hatenablog.com/entry/2020/12/23/201644

コードはこちら

マトリックスをランダムで作成

二部マッチングに使うマトリックスのサイズを大きく可変にしてみました。

width = 120 # マトリックスの幅
height = 120 # マトリックスの高さ

カラムもインデックスも数値だと表示したときわかりづらいので、カラムはアルファベットにしてみました。

内包表現を使って アルファベット2文字の組み合わせ(例: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秒未満 で組み合わせを算出できるのは便利ですね。

以上になります、最後までお読みいただきありがとうございました。

参考サイト

https://myenigma.hatenablog.com/entry/2020/12/23/201644

https://qiita.com/kokorinosoba/items/eb72dac6b68fccbac04d

https://tech-shelf.hatenablog.com/entry/programming/alphabet_list

http://tarao-mendo.blogspot.com/2017/08/numpy-random.html

https://python-ai-learn.com/2021/02/06/seed/

https://zenn.dev/megane_otoko/articles/032_elapsed_time

Discussion