Deferred Acceptance Algorithms

Taneaki Mori



In [1]:
include("deferred_acceptance.jl")


Out[1]:
deferred_acceptance (generic function with 1 method)


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



In [2]:
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[2]:
([1,3,2,4],[1,3,2,4])


次に男性4人、女性3人のランダムな選好について、



In [3]:
include("matching_tools.jl")
m_prefs, f_prefs = random_prefs(4,3)


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

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

In [4]:
deferred_acceptance(m_prefs, f_prefs)


Out[4]:
([2,0,0,1],[4,1,0])


最後に単体テストを実行。



In [5]:
include("test_deferred_acceptance.jl")


Test Summary:                  | Pass  Total
Testing deferred_acceptance.jl |    4      4
Out[5]:
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)