In [37]:
# NUMPYを使って高速化したい
def DA_NUMPY(a, b):
import copy
m_pref = copy.deepcopy(a) #参照渡しでなくコピーを生成するようにした
f_pref = copy.deepcopy(b)
n = len(m_pref) # 男性の数を判定
m = len(f_pref) # 女性の数を判定
unmatch_m = n # 男のunmatch確定を示す数
unmatch_f = m # 女のunmatch確定を示す数
m_engage = [-1] * n # 男性の婚約状態を表す -1は未婚約、それ以外はその数字の女性と婚約中ということ
f_engage = [-1] * m
proposing = -1 # 婚約申し込みを保存しておく
proposed = -1 #婚約申し込まれを保存しておく
while(m_engage.count(-1) != 0):
for proposing in range(n):
if m_engage[proposing] == -1: # 男性が婚約済みの場合は何もしない
proposed = m_pref[proposing][0] # 最も好みの相手に申し込む、と同時に一度申し込んだ相手には二度申し込まない
m_pref[proposing] = m_pref[proposing][1:]+m_pref[proposing][:1]
if proposed == unmatch_f: # unmatch確定のとき
m_engage[proposing] = proposed
elif f_engage[proposed] == -1: #女性が未婚約のとき
if f_pref[proposed].index(proposing) < f_pref[proposed].index(unmatch_m):
f_engage[proposed] = proposing
m_engage[proposing] = proposed
else: #女性が誰かと婚約済みのとき
if f_pref[proposed].index(proposing) < f_pref[proposed].index(f_engage[proposed]):
m_engage[f_engage[proposed]] = -1
m_engage[proposing] = proposed
f_engage[proposed] = proposing
for i in range(m): # 一回も申し込まれないままマッチングが終わった女性のengageを-1からnに変える
if f_engage[i] == -1:
f_engage[i] = n
return m_engage , f_engage
In [ ]:
In [36]:
tes = np.arange(10)
print tes
np.hstack([tes[1:], tes[:1]])
Out[36]:
In [38]:
m_unmatched = 3
f_unmatched = 4
m_prefs = [[0, 1, 2, m_unmatched],
[2, 0, 1, m_unmatched],
[1, 2, 0, m_unmatched],
[2, 0, 1, m_unmatched]]
f_prefs = [[2, 0, 1, 3, f_unmatched],
[0, 1, 2, 3, f_unmatched],
[2, f_unmatched, 1, 0, 3]]
"""
self.m_matched = [0, 1, 2, m_unmatched]
self.f_matched = [0, 1, 2]
"""
print DA(f_prefs,m_prefs)
print DA(m_prefs,f_prefs)
In [27]:
a = [[2,0,4,1,5,3,7,6],
[0,1,2,3,4,5,6,7],
[0,3,4,5,2,6,1,7],
[0,5,6,7,1,2,3,4],
[0,6,5,4,3,2,1,7],
[0,4,6,1,7,2,3,5],
[2,1,6,0,3,4,5,7],
[0,4,6,1,7,2,3,5],
[0,3,4,5,2,6,1,7],
[0,3,4,5,2,6,1,7]]
b = [[0,1,2,3,4,5,6,7,8,9,10],
[0,1,4,5,8,2,3,6,9,10,7],
[0,6,4,5,8,9,10,1,2,3,7],
[6,7,5,4,0,9,1,2,3,8,10],
[2,1,6,0,3,4,5,7,10,8,9],
[0,1,4,5,8,2,3,6,9,10,7],
[0,1,4,5,10,8,2,3,6,9,7]]
DA(a, b)
In [59]:
import numpy as np
n = 10
m = 12
man = np.empty([n,m+1])
woman = np.empty([m,n+1])
for i in range(n):
man[i] = np.arange(m+1)
np.random.shuffle(man[i])
for i in range(m):
woman[i] = np.arange(n+1)
np.random.shuffle(woman[i])
man.tolist()
woman.tolist()
for i in range(n):
for j in range(m+1):
man[i][j] = int(man[i][j])
for i in range(m):
for j in range(n+1):
woman[i][j] = int(woman[i][j])
print man
print woman
DA(man,woman)
In [61]:
# とりあえずtest_matchingは通過したもの、たぶん遅い
def DA(a, b):
import copy
m_pref = copy.deepcopy(a)
f_pref = copy.deepcopy(b)
n = len(m_pref)
m = len(f_pref)
unmatch_m = n
unmatch_f = m
m_engage = [-1] * n
f_engage = [-1] * m
proposing = -1
proposed = -1
while(m_engage.count(-1) != 0):
for proposing in range(n):
if m_engage[proposing] == -1:
proposed = m_pref[proposing].pop(0)
if proposed == unmatch_f:
m_engage[proposing] = proposed
elif f_engage[proposed] == -1:
if f_pref[proposed].index(proposing) < f_pref[proposed].index(unmatch_m):
f_engage[proposed] = proposing
m_engage[proposing] = proposed
else:
if f_pref[proposed].index(proposing) < f_pref[proposed].index(f_engage[proposed]):
m_engage[f_engage[proposed]] = -1
m_engage[proposing] = proposed
f_engage[proposed] = proposing
for i in range(m):
if f_engage[i] == -1:
f_engage[i] = n
return m_engage , f_engage
In [ ]:
In [62]:
a = [[0,1,2,3],
[1,0,2,3],
[1,0,2,3]]
b = [[2,0,1,3],
[2,0,1,3],
[1,2,0,3]]
DA(a, b)
Out[62]:
In [20]:
m_unmatched = 3
f_unmatched = 4
m_prefs = [[0, 1, 2, m_unmatched],
[2, 0, 1, m_unmatched],
[1, 2, 0, m_unmatched],
[2, 0, 1, m_unmatched]]
f_prefs = [[2, 0, 1, 3, f_unmatched],
[0, 1, 2, 3, f_unmatched],
[2, f_unmatched, 1, 0, 3]]
from DA_match import DA
print DA(m_prefs, f_prefs)
print DA(f_prefs, m_prefs)
In [60]:
run test_matching.py
In [ ]:
In [11]:
# 1対多バージョン
import numpy as np
m = 7 # 人の数
n = 3 # 受け入れ先の数
number = [0] * n
for i in range(n):
if i < m%n:
number[i] = m/n+1
else:
number[i] = m/n
print number
In [ ]:
for tested in range(m):
if tested_e[tested] == -1:
testing = tested_p[0]
del tested_p[0]
switch = 0
for i in range(len(testing_e[testing])):
if testing_e[testing][i] == -1:
if switch == 0:
testing_e[testing][i] = tested
tested_e[tested] = testing
switch = 1
if switch = 0: # マッチングを試みた相手に空きがなかった場合ということ
for matched in testing_e:
In [18]:
tested_p = np.empty([m,n])
for i in range(m):
tested_p[i] = np.arange(n)
np.random.shuffle(tested_p[i])
print tested_p
testing_p = np.empty([n,m])
for i in range(n):
testing_p[i] = np.arange(m)
np.random.shuffle(testing_p[i])
print testing_p
tested_e = [-1] * m
testing_e = []
print tested_e
for i in range(n):
testing_e.append([-1]*number[i])
print testing_e