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])


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



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