In [1]:
#とりあえずone-to-one改良しました。
#時間をはかれるようにする
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 [ ]:
In [ ]:
#とりあえず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:
break
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 [ ]:
#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 [ ]:
#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 [ ]:
#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 [ ]:
#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)
In [ ]:
#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]