Repository navigation
Expand file tree
/
Copy pathgaleshapley.lua
More file actions
68 lines (65 loc) · 1.37 KB
/
Copy pathgaleshapley.lua
File metadata and controls
68 lines (65 loc) · 1.37 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
local _, G = ...
local function asPrefList(a, b)
local allList = true
for _, x in pairs(a) do
allList = allList and type(x) == 'table'
end
if allList then
return a
end
local aa = {}
for n, f in pairs(a) do
local bns = {}
for bn in pairs(b) do
table.insert(bns, bn)
end
table.sort(bns, f)
aa[n] = bns
end
return aa
end
local function asPrefFunction(a)
local allFunc = true
for _, x in pairs(a) do
allFunc = allFunc and type(x) == 'function'
end
if allFunc then
return a
end
local aa = {}
for n, bns in pairs(a) do
local ranks = {}
for i, bn in ipairs(bns) do
ranks[bn] = i
end
aa[n] = function(x, y)
return ranks[x] < ranks[y]
end
end
return aa
end
G.StableMarriage = function(men, women)
local tmen = asPrefList(men, women)
local fwomen = asPrefFunction(women, men)
local freeMen = {}
local nextPref = {}
for man in pairs(tmen) do
freeMen[man] = true
nextPref[man] = 1
end
local engagements = {}
for man in next, freeMen do
local prefs = tmen[man]
local idx = nextPref[man]
local woman = prefs[idx]
nextPref[man] = idx + 1
local fiance = engagements[woman] or man
if fwomen[woman](man, fiance) then
freeMen[fiance] = true
fiance = man
end
engagements[woman] = fiance
freeMen[fiance] = nil
end
return engagements
end