In [1]:
Pkg.checkout("MyMatchingA")
In [2]:
Pkg.test("MyMatchingA")
In [9]:
module MyMatchingA
export my_deferred_acceptance
# 多対一のケース
function my_deferred_acceptance(prop_prefs::Array{Int64,2}, resp_prefs::Array{Int64,2}, caps::Array{Int64,1})
m = size(prop_prefs, 2)
n = size(resp_prefs, 2)
prop_matches = fill(-1, m)
prop_next_to_propose = ones(Int64, m)
L = sum(caps)
resp_matches = zeros(Int64, L)
indptr = Array(Int,n+1)
indptr[1] = 1
for i in 1:n
indptr[i+1] = indptr[i] + caps[i]
end
resp_rankings = (m+1)*ones(Int, m, n)
for j in 1:n
for i in 1:length(resp_prefs[j])
b = length(resp_prefs[j])
a = resp_prefs[j][i]
resp_rankings[a,j] = i
end
end
while true
i = get_single(prop_matches)
if i == 0
break
end
if prop_next_to_propose[i] > length(prop_prefs[i])
prop_matches[i] = 0
continue
end
#学生iが入りたい大学jを探す．
j = prop_prefs[i][prop_next_to_propose[i]]
#if j == 0
# prop_matches[i] = 0
# continue
#end
#大学jのリストを探す
#要修正？
p = resp_matches[indptr[j]:indptr[j+1]-1]
if resp_rankings[i,j] >= m+1
prop_next_to_propose[i] += 1
continue
end
#大学jが受け入れ可能なら受け入れる．
a = findfirst(p,0)
if a != 0
resp_matches[indptr[j]-1+a] = i
prop_matches[i] = j
#大学jが定員オーバーしている場合
else
#大学jがiの方を選好していれば，受け入れる．
list_comp = Array(Int, length(p))
for k in 1:length(p)
b = resp_rankings[p[k],j]
list_comp[k] = b
end
b_max = maximum(list_comp)
c = findfirst(resp_rankings[:,j], b_max)
if resp_rankings[i,j] < resp_rankings[c,j]
d = findfirst(resp_matches, c)
resp_matches[d] = i
prop_matches[i] = j
prop_matches[c] = -1
end
end
prop_next_to_propose[i] += 1
end
return prop_matches, resp_matches, indptr
end
#どこにも決まってない学生を返す．(存在しなければ0)
function get_single(partners)
m = size(partners, 1)
for i in 1:m
if partners[i] == -1
return i
end
end
return 0
end
end
# 一対一のケース
function my_deferred_acceptance1(prop_prefs::Array{Int64,2},resp_prefs::Array{Int64,2})
caps = ones(Int, size(resp_prefs, 2))
prop_matches, resp_matches, indptr =
my_deferred_acceptance(prop_prefs, resp_prefs, caps)
return prop_matches, resp_matches
end
Out[9]:
In [3]:
using MyMatchingA
In [4]:
prop_prefs = [3 1 3 1;
1 2 2 2;
2 3 1 3;
0 0 0 0]
Out[4]:
In [3]:
prop_prefs=Array{Int}[[3,1,2,0],[1,2,3,0],[3,2,1,0],[1,2,3,0]]
Out[3]:
In [4]:
prop_prefs = [3 1 2 0;
1 2 3 0;
3 2 1 0;
1 2 3 0]
Out[4]:
In [5]:
resp_prefs = [4 4 4;
1 1 2;
3 2 1;
2 3 3;
0 0 0]
Out[5]:
In [12]:
resp_prefs = Array{Int}[[4,1,3,2,0],[4,1,2,3,0],[4,2,1,3,0]]
Out[12]:
In [5]:
resp_prefs = [4 1 3 2 0;
4 1 2 3 0;
4 2 1 3 0]
Out[5]:
In [ ]:
In [6]:
caps = [2,3,2]
Out[6]:
In [15]:
typeof(prop_prefs)
Out[15]:
In [16]:
typeof(resp_prefs)
Out[16]:
In [17]:
typeof(caps)
Out[17]:
In [7]:
deferred_acceptanceA(prop_prefs,resp_prefs,caps)
In [35]:
list_comp = Array(Int, 3)
Out[35]:
In [36]:
typeof(findfirst(caps,2))
Out[36]:
In [37]:
using Matching
In [38]:
deferred_acceptance(prop_prefs,resp_prefs,caps)
In [39]:
typeof(size(prop_prefs, 2))
Out[39]:
In [40]:
size(resp_prefs, 2)
Out[40]:
In [41]:
m = size(prop_prefs, 2)
n = size(resp_prefs, 2)
Out[41]:
In [42]:
prop_matches = fill(-1, m)
Out[42]:
In [43]:
prop_next_to_propose = ones(Int64, m)
Out[43]:
In [44]:
L = sum(caps)
resp_matches = zeros(Int64, L)
Out[44]:
In [45]:
indptr = Array(Int,n+1)
indptr[1] = 1
for i in 1:n
indptr[i+1] = indptr[i] + caps[i]
end
In [46]:
typeof(indptr)
Out[46]:
In [48]:
resp_rankings = (m+1)*ones(Int, m, n)
for j in 1:n
for i in 1:length(resp_prefs[j])
b = length(resp_prefs[j])
a = resp_prefs[j][i]
resp_rankings[a,j] = i
end
end
In [49]:
typeof(resp_rankings)
Out[49]:
In [50]:
resp_rankings
Out[50]:
In [ ]: