SHARE
TWEET

Untitled

a guest Jul 18th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # -*- coding: utf-8-unix -*-
  2.  
  3. def match_marriage(rank_from_b, rank_from_g):
  4.     """Match boys and girls in stable manner"""
  5.     match = {}
  6.  
  7.     # 女性が指定しなかった男性に与える(最下位の)ランキング値
  8.     rank_end = len(rank_from_g) + 1000
  9.    
  10.     girls = list(rank_from_g.keys())
  11.     boys  = list(rank_from_b.keys())
  12.  
  13.     while boys:
  14.         bid = boys.pop(0)
  15.  
  16.         # 求婚したい先
  17.         favs = rank_from_b[bid]
  18.        
  19.         # その他の候補も加えたリスト
  20.         favs_and_rest = favs + list(set(girls) - set(favs))
  21.  
  22.         # 求婚したい順に申し込んでみる
  23.         for gid in favs_and_rest:
  24.             # 現在の仮婚約者(いれば)
  25.             cur = match.get(gid)
  26.  
  27.             # 未婚約なら仮婚約成立。次の男性のターンへ
  28.             if cur is None:
  29.                 match[gid] = bid
  30.                 break
  31.  
  32.             # 仮婚約済なので、女性視点でどちらがいいか比較する
  33.             else:
  34.                 # 女性側から見た、現在の仮婚約者と新規求婚者のランク(ランク外の場合は外れ値を使う)
  35.                 ranking = rank_from_g[gid]
  36.                 rank_cur = ranking.index(cur) if cur in ranking else rank_end
  37.                 rank_new = ranking.index(bid) if bid in ranking else rank_end
  38.  
  39.                 # 求婚者のランクが上から、そちらに乗り換える。乗り換えられた男性はやり直しへ
  40.                 if rank_new < rank_cur:
  41.                     match[gid] = bid
  42.                     boys.append(cur)
  43.                     break
  44.  
  45.     return match
  46.  
  47. def match_hospital(rank_from_r, rank_from_h, nmax_at_h={}):
  48.     """Match residents and hospitals in stable manner"""
  49.  
  50.     # 各病院の枠を初期化する
  51.     match = dict([(hid, []) for hid in rank_from_h.keys()])
  52.  
  53.     # 病院から認知されていないレジデントに与える最下位のランキング値
  54.     rank_end = len(rank_from_r) + 1000
  55.  
  56.     hospitals = list(rank_from_h.keys())
  57.     residents = list(rank_from_r.keys())
  58.  
  59.     while residents:
  60.         rid = residents.pop(0)
  61.  
  62.         # 働きたい先
  63.         favs = rank_from_r[rid]
  64.  
  65.         # その他の候補も加えたリスト
  66.         favs_and_rest = favs + list(set(hospitals) - set(favs))
  67.  
  68.         # 働きたい順に申し込んでみる
  69.         for hid in favs_and_rest:
  70.             # 現在の空き状況
  71.             status = match[hid]
  72.             ranking = rank_from_h[hid]
  73.  
  74.             # 応募者を加え、病院側から見た候補者ランキング順にならべ直す
  75.             wanted = sorted(status + [rid], key=lambda rid: ranking.index(rid) if rid in ranking else rank_end)
  76.  
  77.             # この病院の受け入れ可能人数(デフォルト2名)
  78.             nmax = nmax_at_h.get(hid) or 2
  79.  
  80.             # 枠が空いていたなら仮編入。次の人のターンへ
  81.             if len(wanted) <= nmax:
  82.                 match[hid] = wanted
  83.                 break
  84.             # 枠以上に応募があるので、誰かを落とす
  85.             else:
  86.                 match[hid] = wanted[0:nmax]
  87.                
  88.                 # 応募者が入れたなら、落ちた人を列に並べ直して次の人のターンへ
  89.                 if rid in match[hid]:
  90.                     residents.append(wanted[nmax])
  91.                     break
  92.  
  93.     return match
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top