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

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



In [4]:

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









    Out[4]:





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



In [5]:

    
my_deferred_acceptance(m_prefs1, f_prefs1)









    Out[5]:





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

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



In [6]:

    
m_prefs2, f_prefs2 = random_prefs(8, 8)









    Out[6]:





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

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



In [7]:

    
my_deferred_acceptance(m_prefs2, f_prefs2)









    Out[7]:





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

3) 単体テストの実行



In [8]:

    
Pkg.test("MyMatching")









    



INFO: Testing MyMatching
INFO: MyMatching tests passed