Deferred Acceptance Algorithms

Taneaki Mori

``````

In [14]:

include("deferred_acceptance.jl")

``````
``````

Out[14]:

deferred_acceptance (generic function with 1 method)

``````

code: https://github.com/taneaki/matching.jl/blob/master/deferred_acceptance.jl

まずは、wikipediaに挙げられている例をやってみる。

``````

In [11]:

m_prefs = [1 3 1 3; 2 2 2 1; 3 1 4 4; 4 4 3 2; 0 0 0 0]
f_prefs = [1 2 2 1; 2 1 3 4; 3 4 1 3; 4 3 4 2; 0 0 0 0]
deferred_acceptance(m_prefs, f_prefs)

``````
``````

Out[11]:

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

``````

``````

In [28]:

include("matching_tools.jl")
m_prefs, f_prefs = random_prefs(4,3)

``````
``````

Out[28]:

(
4x4 Array{Int64,2}:
1  1  2  1
3  0  1  2
2  2  3  3
0  3  0  0,

5x3 Array{Int64,2}:
3  1  2
0  3  1
2  2  3
1  4  0
4  0  4)

``````
``````

In [29]:

deferred_acceptance(m_prefs, f_prefs)

``````
``````

Out[29]:

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

``````

``````

In [30]:

include("test_deferred_acceptance.jl")

``````
``````

Test Summary:                  | Pass  Total
Testing deferred_acceptance.jl |    4      4

Out[30]:

BaseTestNext.DefaultTestSet("Testing deferred_acceptance.jl",Any[BaseTestNext.DefaultTestSet("deferred_acceptance",Any[Test Passed
Expression: m_matched_computed == m_matched_expected
Evaluated: [1,2,3,0] == [1,2,3,0],Test Passed
Expression: f_matched_computed == f_matched_expected
Evaluated: [1,2,3] == [1,2,3],Test Passed
Expression: m_matched_computed == m_matched_expected
Evaluated: [1,2,3,0] == [1,2,3,0],Test Passed
Expression: f_matched_computed == f_matched_expected
Evaluated: [1,2,3] == [1,2,3]],false)],false)

``````
``````

In [ ]:

``````