改良点
とある男がプロポーズする際に、好みの女からプロポーズするように修正した
引数の追加
男4人・女3人など、男女の数が同一でないパターンにも対応できるようにした
挙動
入力
python3 gale_shapley.py 3 4
出力
[[3. 1. 0. 2.]
[1. 2. 3. 0.]
[1. 3. 2. 0.]]
[[0. 1. 2.]
[1. 0. 2.]
[2. 1. 0.]
[0. 1. 2.]]
Engaged (0, 2)
Engaged (1, 3)
Already engaged (1, 3)
Engaged (2, 0)
[[0 2]
[1 3]
[2 0]]
import sys
import numpy as np
"""
Original:
http://cielan.hateblo.jp/entry/2016/12/25/193618
"""
def create_priority(n, m):
"""
優先順位が行ごとにシャッフルされたn次正方行列を生成する
:param n: 自グループの次数
:param m: 相手グループの次数
:return: 優先順位行列
"""
data = np.empty([0, m])
priority = np.arange(m)
for i in range(n):
np.random.shuffle(priority)
data = np.vstack([data, priority])
return data
def gale_shapley(a, b):
"""
Gale-Shapley アルゴリズムを用いて安定結婚問題を解く
:param a: 優先順位行列
:param b: 優先順位行列
:return: 結果行列
"""
single_as = {i for i in range(len(a))}
single_bs = {i for i in range(len(b))}
engaged = np.zeros((len(a), len(b)), dtype=bool)
while len(single_as) != 0:
single_a = single_as.pop()
for target_b in np.argsort(a[single_a, :]):
if target_b in single_bs:
engaged[single_a, target_b] = True
single_bs.remove(target_b)
print('Engaged ', (single_a, target_b))
break
else:
engaged_a = np.where(engaged[:, target_b])[0][0]
print('Already engaged ', (engaged_a, target_b))
target_a_list = b[target_b, :]
if np.where(target_a_list == single_a)[0][0] < np.where(target_a_list == engaged_a)[0][0]:
engaged[engaged_a, target_b] = False
single_as.add(engaged_a)
print('Discard ', (engaged_a, target_b))
engaged[single_a, target_b] = True
print('Engaged ', (single_a, target_b))
break
return engaged
if __name__ == '__main__':
MEN_NUM = int(sys.argv[1])
WOMEN_NUM = int(sys.argv[2])
men = create_priority(MEN_NUM, WOMEN_NUM)
print(men)
women = create_priority(WOMEN_NUM, MEN_NUM)
print(women)
result = gale_shapley(men, women)
print(np.transpose(np.where(result)))