受入保留アルゴリズム

津島亮太



In [1]:

    
using MyMatching

関数のコードはこちら。

まずはWikipediaの例を用いてやってみる。



In [2]:

    
m_prefs = [[3], [3, 2, 1], [1, 3, 2], [3, 1]];



In [3]:

    
f_prefs = [[2, 3], [2, 3, 4, 1], [4, 1, 2]];



In [4]:

    
my_deferred_acceptance(m_prefs, f_prefs)









    Out[4]:





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

できました。次にランダム選好リストを生成する関数を用いてやってみる。



In [5]:

    
using Matching



In [6]:

    
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[6]:





mat2vecs (generic function with 1 method)



In [7]:

    
m_prefs2, f_prefs2 = mat2vecs.(random_prefs(5, 4, allow_unmatched=false))









    Out[7]:





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



In [8]:

    
my_deferred_acceptance(m_prefs2, f_prefs2)









    Out[8]:





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

これも望ましい結果が返されました。最後にテストが通るか試します。



In [9]:

    
Pkg.test("MyMatching")









    



INFO: Testing MyMatching
INFO: MyMatching tests passed

通りました。