次は，(新たな関数を書くのではなく) 課題2 で作った関数に many-to-one マッチング (college admission のケース) を扱う機能を加えましょう．
- 提出方法：課題2で作ったリポジトリに「プッシュ」する．
- 締め切り：
6月27日 (土)7月4日 (土)
次のような状況に限定することにしましょう：
- 学生は高々一つの大学に入る．
- 大学にはそれぞれ受け入れ上限がある．
- 各大学は (グループではなく) 学生それぞれに対して選好を持つ．
- とりあえず，学生側から提案するということにしましょう．
学生の数 m，大学の数 n として，
-
prop_prefs:mx(n+1)の2次元配列 -
resp_prefs:nx(m+1)の2次元配列 -
caps: 長さnの1次元配列
caps[j]は大学jの受入上限
(prop_prefs, resp_prefs はいままでの m_prefs, f_prefs と同じ．)
関数は
def deferred_acceptance(prop_prefs, resp_prefs, caps=None):
...のように書いて，deferred_acceptance(prop_prefs, resp_prefs) のように
caps 引数なしで呼び出されたら一対一としていままでと全く同じように処理するようにする．
とりあえず以下のようなデータ構造を採用することにしましょう．
caps が指定されなければいままで通り
-
prop_matched: 長さmの1次元配列 -
resp_matched: 長さnの1次元配列
を返す
(prop_matched, resp_matched はいままでの m_matched, f_matched と同じ)．
caps が指定されたら次の3つを返す：
-
prop_matched: 長さmの1次元配列 -
resp_matched: 長さLの1次元配列
大学側が受け入れる学生をすべて列挙する． -
indptr: 長さn+1の1次元配列
resp_matched[indptr[j]:indptr[j+1]]が大学jが受け入れる学生のリスト．
ただし，L = sum(caps) です．
indptr は np.cumsum(caps) で得られる長さ n の1次元配列の先頭に 0 を加えたものです．
たとえば，
indptr = np.empty(n+1, dtype=int)
indptr[0] = 0
np.cumsum(caps, out=indptr[1:])で作ることができます．
caps あるなしで indptr の定義を変える，あるいは caps あるなしで
return するもの変えるのは，たとえば次のようにするとできます．
def deferred_acceptance(prop_prefs, resp_prefs, caps=None):
...
if caps is None:
indptr = np.arange(n+1)
else:
indptr = np.empty(n+1, dtype=int)
indptr[0] = 0
np.cumsum(caps, out=indptr[1:])
...
if caps is None:
return prop_matches, resp_matches
else:
return prop_matches, resp_matches, indptrcaps が None のときは caps を定義せずに indptr をメインのループで使うことにして，
最後の if 文で caps が None であるかの判定に使えるようにしています．
(ここで n は大学 (respondants) の数です．自分のコードでは適切な変数名に書きかえる．)
ちなみに，一番最後の else はなくてもよいです．
if caps is None:
return prop_matches, resp_matches
return prop_matches, resp_matches, indptrtest_matching.py に多対一マッチング用のテストを加えました． 作業フォルダにダウンロード，これが通るようにコードを書いていく．
(test_matching.py を修正しました．2015/6/23)
ランダムな caps も返すように
matching_tools.py
の random_prefs を拡張しました．