Deferred Acceptance Algorithm (many-to-one)

Taneaki Mori



In [1]:

    
using MyMatching

1) Input: Vector of Vectors

1-1)one-to-oneの例



In [2]:

    
prop_prefs = [[1, 2, 3, 4], [3, 2, 1, 4], [1, 2, 4, 3], [3, 1, 4, 2]]
resp_prefs = [[1, 2, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [1, 4, 3, 2]]
my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[2]:





([1, 3, 2, 4], [1, 3, 2, 4])

1-2) many-to-oneの例



In [3]:

    
prop_prefs = [[2], [2, 1], [2, 1], [1, 2, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 1, 4, 3], [4, 2, 1, 3]]
resp_prefs = [[3, 7], [7, 8, 5, 1, 2, 3, 4, 6], [2, 5, 8, 1, 3, 4, 7], [2, 5, 1, 3, 6, 4, 7]]
caps = [2, 2, 2, 2]
my_deferred_acceptance(prop_prefs, resp_prefs, caps)









    Out[3]:





([0, 0, 1, 3, 4, 4, 2, 2], [3, 0, 7, 8, 4, 0, 5, 6], [1, 3, 5, 7, 9])

2) Input: Matrix

2-1) one-to-oneの例



In [4]:

    
prop_prefs = 
[3  3  2  3;
 0  0  1  2;
 1  2  0  0;
 2  1  3  1]
resp_prefs = 
[ 3  3  3;
 4  4  4;
 0  2  2;
 2  1  0;
 1  0  1]
my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[4]:





([0, 0, 2, 3], [0, 3, 4])

2-2) many-to-oneの例



In [5]:

    
caps = [2,2,2]
my_deferred_acceptance(prop_prefs, resp_prefs, caps)









    Out[5]:





([0, 3, 2, 3], [0, 0, 3, 0, 2, 4], [1, 3, 5, 7])

3) 単体テストの実行



In [6]:

    
Pkg.test("MyMatching")









    



INFO: Testing MyMatching






    



Test Summary:               | Pass  Total
Testing deferred acceptance |   36     36






    



INFO: MyMatching tests passed