Deferred Acceptance Algorithm (one-to-one)

Taneaki Mori



In [1]:

    
using Matching



In [2]:

    
function mat2vecs{T<:Integer}(prefs::Matrix{T})
    return [prefs[1:findfirst(prefs[:, j], 0)-1, j] for j in 1:size(prefs, 2)]
end









    Out[2]:





mat2vecs (generic function with 1 method)



In [3]:

    
using MyMatching









    



WARNING: requiring "MyMatching" in module "Main" did not define a corresponding module.

1) 入力データがVector{Vector}の場合



In [4]:

    
m_prefs1, f_prefs1 = mat2vecs.(random_prefs(8, 8))









    Out[4]:





(Array{Int64,1}[[3,7,1],[7],[2,5,4,3,7,8,1,6],[5,3,2],[8,3,6,2,5,4,1],[7,3,4,6,5],[4],[1,3,8]],Array{Int64,1}[[2,7,6,4,5],[2,5,4,1],[6],[5,7,8,2,1],[1,7],[6],[3,4,7,8,5,2],[3,7,5]])



In [5]:

    
my_deferred_acceptance(m_prefs1, f_prefs1)









    Out[5]:





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

2) 入力データがMatrixの場合



In [6]:

    
m_prefs2, f_prefs2 = random_prefs(8, 8)









    Out[6]:





(
[3 8 … 1 2; 1 7 … 7 4; … ; 2 4 … 4 6; 6 1 … 2 0],

[7 2 … 8 5; 3 5 … 6 2; … ; 4 1 … 7 3; 8 4 … 2 1])



In [7]:

    
my_deferred_acceptance(m_prefs2, f_prefs2)









    Out[7]:





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

3) 単体テストの実行



In [8]:

    
Pkg.test("MyMatching")









    



INFO: Testing MyMatching
INFO: MyMatching tests passed