In [1]:
#ランダムな選考の作成
from matching_tools import random_prefs
In [2]:
import numpy as np
In [6]:
m_prefs, f_prefs = random_prefs(15, 3)
In [8]:
m_prefs
Out[8]:
In [81]:
b=[]
for i in m_prefs[3]:
print i
b.append(i)
print b
In [9]:
f_prefs
Out[9]:
In [21]:
np.argsort(f_prefs)
Out[21]:
In [108]:
#many-to-one matching をやってみる前に,遅かったのでone-to-oneを改善
#辞書はあくまで使わない方針で
#変数名はわかりやすいほうがいいので面倒くさがらず書く
#argsortはすごい便利
#できればリスト内包表記に
def da0(m_pref_input,f_pref_input):
#まずはnumpy のarrayに変換する
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
#受け入れ側の選考リストを申し込み側の番号の場所に申し込み側の被選考順序が書いてある状態にする
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
#未マッチのリスト
free=list(range(m_popu))
#マッチングリストを作成。-1が初期値
m_match=np.tile([-1],m_popu)
f_match=np.tile([-1],f_popu)
#こっからメインのループ
while len(free) > 0:
applyman = free.pop()
print applyman
apply_prefs=m_pref_array[applyman]
#apply側の選考をみる
for prefered in apply_prefs:
print prefered
print m_match
print f_match
if prefered == f_popu:
m_match[applyman]=f_popu
break
else:
prefered_pref = f_prefsort[prefered]
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match < rank_apply:
continue
else:
matched_man=f_match[prefered]
if matched_man==-1:
m_match[applyman]=prefered
f_match[prefered]=applyman
break
else:
rank_matched=prefered_pref[matched_man]
if rank_apply < rank_matched:
m_match[applyman]=prefered
f_match[prefered]=applyman
m_match[matched_man]=-1
free.append(matched_man)
break
#for文を入れればelseはいらない
for i in range(f_popu):
if f_match[i] == -1:
f_match[i]=m_popu
return [m_match,f_match]
In [87]:
a=np.array([[0,1,2,3],[2,0,1,3],[1,2,0,3],[2,0,1,3]])
b=np.array([[2,0,1,3,4],[0,1,2,3,4],[2,4,1,0,3]])
In [88]:
a
Out[88]:
In [93]:
np.argsort(b)
Out[93]:
In [109]:
#テスト成功
da0(a,b)
Out[109]:
In [110]:
import time
In [120]:
#時間をはかれるようにする
def da0(m_pref_input,f_pref_input):
start=time.time()
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
#受け入れ側の選考リストを申し込み側の番号の場所に申し込み側の被選考順序が書いてある状態にする
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
#未マッチのリスト
free=list(range(m_popu))
#マッチングリストを作成。-1が初期値
m_match=np.tile([-1],m_popu)
f_match=np.tile([-1],f_popu)
#こっからメインのループ
while len(free) > 0:
applyman = free.pop()
apply_prefs=m_pref_array[applyman]
#apply側の選考をみる
for prefered in apply_prefs:
if prefered == f_popu:
m_match[applyman]=f_popu
break
else:
prefered_pref = f_prefsort[prefered]
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match < rank_apply:
continue
else:
matched_man=f_match[prefered]
if matched_man==-1:
m_match[applyman]=prefered
f_match[prefered]=applyman
break
else:
rank_matched=prefered_pref[matched_man]
if rank_apply < rank_matched:
m_match[applyman]=prefered
f_match[prefered]=applyman
m_match[matched_man]=-1
free.append(matched_man)
break
#for文を入れればelseはいらない
for i in range(f_popu):
if f_match[i] == -1:
f_match[i]=m_popu
elapsed_time = time.time() - start
print elapsed_time
return [m_match,f_match]
In [121]:
da0(a,b)
Out[121]:
In [127]:
#たくさんでやってみる
c,d = random_prefs(1000,1000)
In [128]:
da0(c,d) #速いのか？
Out[128]:
In [21]:
#とりあえずmany-to-oneのコードに変更する。
#capsは長さnの一次元配列（i番目がfemale_iの受け入れ人数）
#別にcapsの要素に制限はない
#出力はmatching_list二つと、i番目までのfemaleが受け入れたmaleの数を累積で記し、冒頭に0を加えたindptrの三つ
#方針は二つ。①最初から長さlのリストを作っておいて、indptrと関連させながら動かす
#②各femaleでcaps分のlistを作り、呼び出しながら使う
#とりあえず②の方針で
import numpy as np
import time
def deferred_acceptance(m_pref_input,f_pref_input,caps):
start=time.time()
#とりまnp_arrayに変換
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
caps_array=np.array(caps)
#受け入れ側の選考リストを申し込み側の番号の場所に申し込み側の被選考順序が書いてある状態にする
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
#未マッチのリスト
free=list(range(m_popu))
#マッチングリストを作成。-1が初期値
m_match=np.tile([-1],m_popu)
#n個の空のリストを辞書にくっつける
f_accept = {}
for i in range(f_popu):
f_accept[i] = []
#こっからメインのループ
while len(free) > 0:
applyman = free.pop()
apply_prefs=m_pref_array[applyman]
#apply側の選考をみる
for prefered in apply_prefs:
if prefered == f_popu:
m_match[applyman]=f_popu
break
else:
prefered_pref = f_prefsort[prefered]
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match < rank_apply:
continue
#ここまでのループ処理はone-to-oneと同じ
else:
#もしpreferedのcapsがオーバーしていなかったら
prefered_accept = f_accept[prefered]
if len(prefered_accept) < caps[prefered]:
m_match[applyman]=prefered
#prefered_acceptの中は右に行くほどpreferedに取って望ましくない奴がいるようにしたい
if len(prefered_accept) == 0:
prefered_accept.append(applyman)
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already < rank_apply:
continue
else:
prefered_accept.insert(i,applyman)
break
#もしpreferedのcapsいっぱいに人が入っていたら
else:
#ここははなから後ろのやつからランク見て適切な場所に入れるように改良
last_man = prefered_accept[-1]
rank_last_man=prefered_pref[last_man]
if rank_apply < rank_last_man:
m_match[applyman]=prefered
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already < rank_apply:
break
else:
prefered_accept.insert(i,applyman)
m_match[last_man]=-1
free.append(last_man)
break
#capsに満たなかったfのacceptに不足分だけのunmatch番号を加える
for i in range(f_popu):
f_indi = f_accept[i]
gap = caps[i] - len(f_indi)
if gap > 0:
residual = [m_popu] * gap
f_indi.extend(residual)
continue
#f_acceptの各リストを結合してf_matchにする
f_match = []
for i in range(f_popu):
f_match.extend(f_accept[i])
#最後にindptrの作成
indptr = np.cumsum(caps)
l_indptr = list(indptr)
l_indptr.insert(0,0)
elapsed_time = time.time() - start
print elapsed_time
return [list(m_match),f_match,l_indptr]
In [22]:
caps = [4,3,5]
deferred_acceptance(m_prefs,f_prefs,caps)
Out[22]:
In [3]:
#テストが通らないので直す
#直せない
import numpy as np
def deferred_acceptance(m_pref_input,f_pref_input,caps):
#こっから
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
caps_array=np.array(caps)
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
free=list(range(m_popu))
m_match=np.tile([f_popu],m_popu)
f_accept = {}
for i in range(f_popu):
f_accept[i] = []
#ここまで準備
#こっからメインループ
while len(free) > 0:
applyman = free.pop()
#print applyman
apply_prefs=m_pref_array[applyman]
#print apply_prefs
for prefered in apply_prefs:
#print prefered
if prefered == f_popu:
m_match[applyman]=f_popu
#print m_match
break
else:
prefered_pref = f_prefsort[prefered]
#print prefered_pref
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match > rank_apply:
prefered_accept = f_accept[prefered]
#print prefered_accept
if len(prefered_accept) < caps[prefered]:
if len(prefered_accept) == 0:
prefered_accept.append(applyman)
#print prefered_accept
m_match[applyman] = prefered
#print m_match
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
#print prefered_accept
m_match[applyman] = prefered
#print m_match
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
#print prefered_accept
unmatch_man = prefered_accept.pop()
#print unmatch_man
m_match[unmatch_man]=f_popu
m_match[applyman] = prefered
#print m_match
free.append(unmatch_man)
#print free
break
break
for i in range(f_popu):
f_indi = f_accept[i]
gap = caps[i] - len(f_indi)
if gap > 0:
residual = [m_popu] * gap
f_indi.extend(residual)
f_match = []
for i in range(f_popu):
f_match.extend(f_accept[i])
indptr = np.cumsum(caps)
l_indptr = list(indptr)
l_indptr.insert(0,0)
return [list(m_match),f_match,l_indptr]
In [4]:
s_unmatched=5
s_prefs =np.array( [[2, 0, 4, 3, s_unmatched, 1],
[0, 2, 3, 1, 4, s_unmatched],
[3, 4, 2, 0, 1, s_unmatched],
[2, 3, 0, 4, s_unmatched, 1],
[0, 3, 1, s_unmatched, 2, 4],
[3, 2, 1, 0, 4, s_unmatched],
[1, 4, 0, 2, s_unmatched, 3],
[0, 2, 1, 4, 3, s_unmatched],
[3, 0, 4, s_unmatched, 1, 2],
[2, 0, 4, 1, 3, s_unmatched],
[4, 3, 0, 2, 1, s_unmatched]])
In [5]:
c_unmatched = 11
c_prefs = [[2, 6, 8, 10, 4, 3, 9, 7, 5, 0, 1, c_unmatched],
[4, 6, 9, 5, 7, 1, 2, 10, c_unmatched, 0, 3, 8],
[10, 5, 7, 2, 1, 3, 6, 0, 9, c_unmatched, 4, 8],
[9, 0, 1, 10, 3, 8, 4, 2, 5, 7, c_unmatched, 6],
[1, 3, 9, 6, 5, 0, 7, 2, 10, 8, c_unmatched, 4]]
In [11]:
c=np.array(c_prefs)
In [13]:
d=c.argsort()
d
Out[13]:
In [6]:
caps = [4, 1, 3, 2, 1]
deferred_acceptance(s_prefs,c_prefs,caps)
Out[6]:
In [90]:
a=[0,1,2]
a
Out[90]:
In [97]:
b=a.reverse()
print b
In [85]:
#修正する
#とりあえずok
def da_00(m_pref_input,f_pref_input,caps):
#こっから
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
caps_array=np.array(caps)
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
free=list(range(m_popu))
m_match=np.tile([f_popu],m_popu)
f_accept = {}
for i in range(f_popu):
f_accept[i] = []
#ここまで準備
#こっからメインループ
while len(free) > 0:
applyman = free.pop()
print applyman
apply_prefs=m_pref_array[applyman]
print apply_prefs
for prefered in apply_prefs:
print prefered
if prefered == f_popu:
m_match[applyman]=f_popu
print m_match
break
else:
prefered_pref = f_prefsort[prefered]
print prefered_pref
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match > rank_apply:
prefered_accept = f_accept[prefered]
print prefered_accept
if len(prefered_accept) < caps[prefered]:
if len(prefered_accept) == 0:
prefered_accept.append(applyman)
print prefered_accept
m_match[applyman] = prefered
print m_match
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
m_match[applyman] = prefered
print m_match
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
print prefered_accept
break
else:
if i == len(prefered_accept)-1:
prefered_accept.append(applyman)
print prefered_accept
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
unmatch_man = prefered_accept.pop()
print unmatch_man
m_match[unmatch_man]=f_popu
m_match[applyman] = prefered
print m_match
free.append(unmatch_man)
print free
print prefered_accept
break
if applyman in prefered_accept:
break
else:
continue
for i in range(f_popu):
f_indi = f_accept[i]
gap = caps[i] - len(f_indi)
if gap > 0:
residual = [m_popu] * gap
f_indi.extend(residual)
f_match = []
for i in range(f_popu):
f_match.extend(f_accept[i])
indptr = np.cumsum(caps)
l_indptr = list(indptr)
l_indptr.insert(0,0)
return [list(m_match),f_match,l_indptr]
In [86]:
caps = [4, 1, 3, 2, 1]
da_00(s_prefs,c_prefs,caps)
Out[86]:
In [91]:
#many-to-one完成版
def deferred_acceptance(m_pref_input,f_pref_input,caps):
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
caps_array=np.array(caps)
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
free=list(range(m_popu))
m_match=np.tile([f_popu],m_popu)
f_accept = {}
for i in range(f_popu):
f_accept[i] = []
while len(free) > 0:
applyman = free.pop()
print applyman
apply_prefs=m_pref_array[applyman]
print apply_prefs
for prefered in apply_prefs:
print prefered
if prefered == f_popu:
m_match[applyman]=f_popu
print m_match
break
else:
prefered_pref = f_prefsort[prefered]
print prefered_pref
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match > rank_apply:
prefered_accept = f_accept[prefered]
print prefered_accept
if len(prefered_accept) < caps[prefered]:
if len(prefered_accept) == 0:
prefered_accept.append(applyman)
print prefered_accept
m_match[applyman] = prefered
print m_match
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
m_match[applyman] = prefered
print m_match
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
print prefered_accept
break
else:
if i == len(prefered_accept)-1:
prefered_accept.append(applyman)
print prefered_accept
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
unmatch_man = prefered_accept.pop()
print unmatch_man
m_match[unmatch_man]=f_popu
m_match[applyman] = prefered
print m_match
free.append(unmatch_man)
print free
print prefered_accept
break
if applyman in prefered_accept:
break
else:
continue
for i in range(f_popu):
f_indi = f_accept[i]
gap = caps[i] - len(f_indi)
if gap > 0:
residual = [m_popu] * gap
f_indi.extend(residual)
f_match = []
for i in range(f_popu):
f_match.extend(f_accept[i])
indptr = np.cumsum(caps)
l_indptr = list(indptr)
l_indptr.insert(0,0)
return [list(m_match),f_match,l_indptr]
In [90]:
#caps==NOneに対応・・・できない
def deferred_acceptance(m_pref_input,f_pref_input,caps)
if caps==None:
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
free=list(range(m_popu))
m_match=np.tile([-1],m_popu)
f_match=np.tile([-1],f_popu)
while len(free) > 0:
applyman = free.pop()
print applyman
apply_prefs=m_pref_array[applyman]
for prefered in apply_prefs:
print prefered
print m_match
print f_match
if prefered == f_popu:
m_match[applyman]=f_popu
break
else:
prefered_pref = f_prefsort[prefered]
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match < rank_apply:
continue
else:
matched_man=f_match[prefered]
if matched_man==-1:
m_match[applyman]=prefered
f_match[prefered]=applyman
break
else:
rank_matched=prefered_pref[matched_man]
if rank_apply < rank_matched:
m_match[applyman]=prefered
f_match[prefered]=applyman
m_match[matched_man]=-1
free.append(matched_man)
break
for i in range(f_popu):
if f_match[i] == -1:
f_match[i]=m_popu
return [m_match,f_match]
else:
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
caps_array=np.array(caps)
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
free=list(range(m_popu))
m_match=np.tile([f_popu],m_popu)
f_accept = {}
for i in range(f_popu):
f_accept[i] = []
while len(free) > 0:
applyman = free.pop()
print applyman
apply_prefs=m_pref_array[applyman]
print apply_prefs
for prefered in apply_prefs:
print prefered
if prefered == f_popu:
m_match[applyman]=f_popu
print m_match
break
else:
prefered_pref = f_prefsort[prefered]
print prefered_pref
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match > rank_apply:
prefered_accept = f_accept[prefered]
print prefered_accept
if len(prefered_accept) < caps[prefered]:
if len(prefered_accept) == 0:
prefered_accept.append(applyman)
print prefered_accept
m_match[applyman] = prefered
print m_match
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
m_match[applyman] = prefered
print m_match
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
print prefered_accept
break
else:
if i == len(prefered_accept)-1:
prefered_accept.append(applyman)
print prefered_accept
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
unmatch_man = prefered_accept.pop()
print unmatch_man
m_match[unmatch_man]=f_popu
m_match[applyman] = prefered
print m_match
free.append(unmatch_man)
print free
print prefered_accept
break
if applyman in prefered_accept:
break
else:
continue
for i in range(f_popu):
f_indi = f_accept[i]
gap = caps[i] - len(f_indi)
if gap > 0:
residual = [m_popu] * gap
f_indi.extend(residual)
f_match = []
for i in range(f_popu):
f_match.extend(f_accept[i])
indptr = np.cumsum(caps)
l_indptr = list(indptr)
l_indptr.insert(0,0)
return [list(m_match),f_match,l_indptr]
In [13]:
#Noneに対応？
#時間を図れるように
#各シャープをとれば経過が観れます
import time
def deferred_acceptance(m_pref_input,f_pref_input,caps):
start = time.time()
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
if caps == None:
caps = [1] * f_popu
caps_array=np.array(caps)
free=list(range(m_popu))
m_match=np.tile([f_popu],m_popu)
f_accept = {}
for i in range(f_popu):
f_accept[i] = []
while len(free) > 0:
applyman = free.pop()
#print applyman
apply_prefs=m_pref_array[applyman]
#print apply_prefs
for prefered in apply_prefs:
#print prefered
if prefered == f_popu:
m_match[applyman]=f_popu
#print m_match
break
else:
prefered_pref = f_prefsort[prefered]
#print prefered_pref
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match > rank_apply:
prefered_accept = f_accept[prefered]
#print prefered_accept
if len(prefered_accept) < caps[prefered]:
if len(prefered_accept) == 0:
prefered_accept.append(applyman)
#print prefered_accept
m_match[applyman] = prefered
#print m_match
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
m_match[applyman] = prefered
#print m_match
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
#print prefered_accept
break
else:
if i == len(prefered_accept)-1:
prefered_accept.append(applyman)
#print prefered_accept
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
unmatch_man = prefered_accept.pop()
#print unmatch_man
m_match[unmatch_man]=f_popu
m_match[applyman] = prefered
#print m_match
free.append(unmatch_man)
#print free
#print prefered_accept
break
if applyman in prefered_accept:
break
else:
continue
for i in range(f_popu):
f_indi = f_accept[i]
gap = caps[i] - len(f_indi)
if gap > 0:
residual = [m_popu] * gap
f_indi.extend(residual)
f_match = []
for i in range(f_popu):
f_match.extend(f_accept[i])
indptr = np.cumsum(caps)
l_indptr = list(indptr)
l_indptr.insert(0,0)
end = time.time()
lapse = end - start
if caps == [1] * f_popu:
print lapse
return [list(m_match),f_match]
else:
print lapse
return [list(m_match),f_match,l_indptr]
In [29]:
m_prefs, f_prefs = random_prefs(40, 5)
In [30]:
caps = [8,8,8,8,8]
deferred_acceptance(m_prefs,f_prefs,caps)
Out[30]:
In [60]:
#un_match人数の出力
def deferred_acceptance(m_pref_input,f_pref_input,caps):
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
if caps == None:
caps = [1] * f_popu
caps_array=np.array(caps)
free=list(range(m_popu))
m_match=np.tile([f_popu],m_popu)
f_accept = {}
for i in range(f_popu):
f_accept[i] = []
while len(free) > 0:
applyman = free.pop()
#print applyman
apply_prefs=m_pref_array[applyman]
#print apply_prefs
for prefered in apply_prefs:
#print prefered
if prefered == f_popu:
m_match[applyman]=f_popu
#print m_match
break
else:
prefered_pref = f_prefsort[prefered]
#print prefered_pref
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match > rank_apply:
prefered_accept = f_accept[prefered]
#print prefered_accept
if len(prefered_accept) < caps[prefered]:
if len(prefered_accept) == 0:
prefered_accept.append(applyman)
#print prefered_accept
m_match[applyman] = prefered
#print m_match
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
m_match[applyman] = prefered
#print m_match
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
#print prefered_accept
break
else:
if i == len(prefered_accept)-1:
prefered_accept.append(applyman)
#print prefered_accept
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
unmatch_man = prefered_accept.pop()
#print unmatch_man
m_match[unmatch_man]=f_popu
m_match[applyman] = prefered
#print m_match
free.append(unmatch_man)
#print free
#print prefered_accept
break
if applyman in prefered_accept:
break
else:
continue
for i in range(f_popu):
f_indi = f_accept[i]
gap = caps[i] - len(f_indi)
if gap > 0:
residual = [m_popu] * gap
f_indi.extend(residual)
f_match = []
for i in range(f_popu):
f_match.extend(f_accept[i])
indptr = np.cumsum(caps)
l_indptr = list(indptr)
l_indptr.insert(0,0)
if caps == [1] * f_popu:
count = 0
for i in m_match:
if m_match[i] == f_popu:
count += 1
return count
#print lapse
#return [list(m_match),f_match]
else:
count = 0
for i in m_match:
if m_match[i] == f_popu:
count += 1
return count
#print lapse
#return [list(m_match),f_match,l_indptr]
In [61]:
m_prefs, f_prefs = random_prefs(40, 5)
In [73]:
#unmatch_numberは平均15人もいる。
caps = [8,8,8,8,8]
unmatch_number = []
for i in range(1000):
m_prefs, f_prefs = random_prefs(40, 5)
unmatch_number.append(deferred_acceptance(m_prefs,f_prefs,caps))
np.array(unmatch_number)
np.average(unmatch_number)
Out[73]:
In [10]:
#Noneに対応しました
import time
def deferred_acceptance(m_pref_input,f_pref_input,caps=None):
#start = time.time()
m_pref_array=np.array(m_pref_input)
f_pref_array=np.array(f_pref_input)
f_prefsort=np.argsort(f_pref_array)
m_popu=m_pref_array.shape[0]
f_popu=f_pref_array.shape[0]
if caps == None:
caps = [1] * f_popu
caps_array=np.array(caps)
free=list(range(m_popu))
m_match=np.tile([f_popu],m_popu)
f_accept = {}
for i in range(f_popu):
f_accept[i] = []
while len(free) > 0:
applyman = free.pop()
#print applyman
apply_prefs=m_pref_array[applyman]
#print apply_prefs
for prefered in apply_prefs:
#print prefered
if prefered == f_popu:
m_match[applyman]=f_popu
#print m_match
break
else:
prefered_pref = f_prefsort[prefered]
#print prefered_pref
rank_apply = prefered_pref[applyman]
rank_non_match = prefered_pref[m_popu]
if rank_non_match > rank_apply:
prefered_accept = f_accept[prefered]
#print prefered_accept
if len(prefered_accept) < caps[prefered]:
if len(prefered_accept) == 0:
prefered_accept.append(applyman)
#print prefered_accept
m_match[applyman] = prefered
#print m_match
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
m_match[applyman] = prefered
#print m_match
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
#print prefered_accept
break
else:
if i == len(prefered_accept)-1:
prefered_accept.append(applyman)
#print prefered_accept
break
else:
for i in range(len(prefered_accept)):
rank_already = prefered_pref[prefered_accept[i]]
if rank_already > rank_apply:
prefered_accept.insert(i,applyman)
unmatch_man = prefered_accept.pop()
#print unmatch_man
m_match[unmatch_man]=f_popu
m_match[applyman] = prefered
#print m_match
free.append(unmatch_man)
#print free
#print prefered_accept
break
if applyman in prefered_accept:
break
else:
continue
for i in range(f_popu):
f_indi = f_accept[i]
gap = caps[i] - len(f_indi)
if gap > 0:
residual = [m_popu] * gap
f_indi.extend(residual)
f_match = []
for i in range(f_popu):
f_match.extend(f_accept[i])
indptr = np.cumsum(caps)
l_indptr = list(indptr)
l_indptr.insert(0,0)
#end = time.time()
#lapse = end - start
if caps == [1] * f_popu:
#print lapse
return [list(m_match),f_match]
else:
#print lapse
return [list(m_match),f_match,l_indptr]
In [7]:
m_prefs, f_prefs = random_prefs(15, 3)
In [9]:
caps=[2,3,8]
deferred_acceptance(m_prefs,f_prefs,caps)
Out[9]:
In [ ]: