Many to Manyに拡張



In [62]:

    
Pkg.checkout("MyMatchingA")









    



INFO: Checking out MyMatchingA master...
INFO: Pulling MyMatchingA latest master...
INFO: No packages to install, update or remove



In [63]:

    
using MyMatchingA

one to oneの場合



In [64]:

    
m, n = 5, 4;



In [65]:

    
m_prefs = [
    1, 2, 3, 4, 0,
    4, 2, 3, 1, 0,
    4, 3, 1, 2, 0,
    1, 4, 3, 2, 0,
    1, 2, 4, 0, 3,
]
m_prefs = reshape(m_prefs, n+1, m)
m_prefs = transpose(m_prefs)









    Out[65]:





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



In [66]:

    
f_prefs = [
    2, 3, 1, 4, 5, 0,
    3, 1, 2, 4, 5, 0,
    5, 4, 1, 2, 3, 0,
    1, 4, 5, 2, 3, 0,
]
f_prefs = reshape(f_prefs, m+1, n)
f_prefs = transpose(f_prefs)









    Out[66]:





4×6 Array{Int64,2}:
 2  3  1  4  5  0
 3  1  2  4  5  0
 5  4  1  2  3  0
 1  4  5  2  3  0



In [67]:

    
my_deferred_acceptance(m_prefs, f_prefs)









    Out[67]:





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



In [68]:

    
m = n = 4;



In [69]:

    
m_prefs = [
    1, 2, 3, 4, 0,
    2, 1, 4, 3, 0,
    3, 4, 1, 2, 0,
    4, 3, 2, 1, 0,
]
m_prefs = reshape(m_prefs, n+1, m)
m_prefs = transpose(m_prefs)









    Out[69]:





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



In [70]:

    
f_prefs = [
    4, 3, 2, 1, 0,
    3, 4, 1, 2, 0,
    2, 1, 4, 3, 0,
    1, 2, 3, 4, 0,
]
f_prefs = reshape(f_prefs, m+1, n)
f_prefs = transpose(f_prefs)









    Out[70]:





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



In [71]:

    
my_deferred_acceptance(m_prefs, f_prefs)









    Out[71]:





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



In [72]:

    
my_deferred_acceptance(f_prefs, m_prefs)









    Out[72]:





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

Many to Manyの場合



In [73]:

    
m_caps = fill(2, m)
f_caps = m_caps









    Out[73]:





4-element Array{Int64,1}:
 2
 2
 2
 2



In [74]:

    
m_caps









    Out[74]:





4-element Array{Int64,1}:
 2
 2
 2
 2



In [75]:

    
my_deferred_acceptance(m_prefs, f_prefs, m_caps, f_caps)









    Out[75]:





([1,2,2,1,3,4,4,3],[1,2,1,2,3,4,3,4],[1,3,5,7,9],[1,3,5,7,9])

Many to oneの場合



In [76]:

    
m, n = 7, 5;



In [77]:

    
s_prefs = [
    5, 1, 0, 2, 3, 4,
    2, 5, 1, 0, 3, 4,
    3, 1, 0, 2, 4, 5,
    4, 1, 0, 2, 3, 5,
    1, 2, 0, 3, 4, 5,
    1, 3, 0, 2, 4, 5,
    1, 3, 4, 0, 2, 6,
]
s_prefs = reshape(s_prefs, n+1, m)
s_prefs = transpose(s_prefs)









    Out[77]:





7×6 Array{Int64,2}:
 5  1  0  2  3  4
 2  5  1  0  3  4
 3  1  0  2  4  5
 4  1  0  2  3  5
 1  2  0  3  4  5
 1  3  0  2  4  5
 1  3  4  0  2  6



In [78]:

    
c_prefs = [
    1, 2, 3, 4, 5, 6, 7, 0,
    5, 2, 0, 1, 3, 4, 6, 7,
    6, 7, 3, 0, 1, 2, 4, 5,
    7, 4, 0, 1, 2, 3, 5, 6,
    2, 1, 0, 3, 4, 5, 6, 7,
]
c_prefs = reshape(c_prefs, m+1, n)
c_prefs = transpose(c_prefs)









    Out[78]:





5×8 Array{Int64,2}:
 1  2  3  4  5  6  7  0
 5  2  0  1  3  4  6  7
 6  7  3  0  1  2  4  5
 7  4  0  1  2  3  5  6
 2  1  0  3  4  5  6  7



In [79]:

    
caps = ones(Int, n)
caps[1] = 3
caps









    Out[79]:





5-element Array{Int64,1}:
 3
 1
 1
 1
 1



In [80]:

    
my_deferred_acceptance(s_prefs, c_prefs, caps)









    Out[80]:





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



In [81]:

    
m, n = 11, 5;



In [82]:

    
s_prefs = [
    3, 1, 5, 4, 0, 2,
    1, 3, 4, 2, 5, 0,
    4, 5, 3, 1, 2, 0,
    3, 4, 1, 5, 0, 2,
    1, 4, 2, 0, 3, 5,
    4, 3, 2, 1, 5, 0,
    2, 5, 1, 3, 0, 4,
    1, 3, 2, 5, 4, 0,
    4, 1, 5, 0, 2, 3,
    3, 1, 5, 2, 4, 0,
    5, 4, 1, 3, 2, 0,
]
s_prefs = reshape(s_prefs, n+1, m)
s_prefs = transpose(s_prefs)









    Out[82]:





11×6 Array{Int64,2}:
 3  1  5  4  0  2
 1  3  4  2  5  0
 4  5  3  1  2  0
 3  4  1  5  0  2
 1  4  2  0  3  5
 4  3  2  1  5  0
 2  5  1  3  0  4
 1  3  2  5  4  0
 4  1  5  0  2  3
 3  1  5  2  4  0
 5  4  1  3  2  0



In [83]:

    
c_prefs = [
    3, 7, 9, 11, 5, 4, 10, 8, 6, 1, 2, 0,
    5, 7, 10, 6, 8, 2, 3, 11, 0, 1, 4, 9,
    11, 6, 8, 3, 2, 4, 7, 1, 10, 0, 5, 9,
    10, 1, 2, 11, 4, 9, 5, 3, 6, 8, 0, 7,
    2, 4, 10, 7, 6, 1, 8, 3, 11, 9, 0, 5,
]
c_prefs = reshape(c_prefs, m+1, n)
c_prefs = transpose(c_prefs)









    Out[83]:





5×12 Array{Int64,2}:
  3  7   9  11  5  4  10   8   6  1  2  0
  5  7  10   6  8  2   3  11   0  1  4  9
 11  6   8   3  2  4   7   1  10  0  5  9
 10  1   2  11  4  9   5   3   6  8  0  7
  2  4  10   7  6  1   8   3  11  9  0  5



In [84]:

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



In [85]:

    
my_deferred_acceptance(s_prefs, c_prefs, caps)









    Out[85]:





([3,1,4,3,1,3,2,1,4,1,5],[2,5,8,10,7,1,4,6,3,9,11],[1,2,3,4,5,6,7,8,9,10,11,12],[1,5,6,9,11,12])

ソースコード(https://github.com/akihirosasaki/MyMatchingA.jl/blob/master/src/MyMatchingA.jl)

caps内で順番が前後していることがあるので、最終的にランキング順に並べるコードを追加できればなお良いかなと思いました。

あと、１次元配列だと直感的に分かりづらいのが、問題かなと思いました。



In [ ]: