Stable marriage problem: Difference between revisions
Content added Content deleted
(Add Nim solution) |
(Added Wren) |
||
Line 7,799: | Line 7,799: | ||
ian - hope |
ian - hope |
||
jan - abi |
jan - abi |
||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Go}} |
|||
{{libheader|Wren-dynamic}} |
|||
Although this is a faithful translation, the results are not identical to those of Go as map iteration order in both languages is undefined. |
|||
<lang ecmascript>import "/dynamic" for Struct |
|||
var mPref = { |
|||
"abe": [ |
|||
"abi", "eve", "cath", "ivy", "jan", |
|||
"dee", "fay", "bea", "hope", "gay"], |
|||
"bob": [ |
|||
"cath", "hope", "abi", "dee", "eve", |
|||
"fay", "bea", "jan", "ivy", "gay"], |
|||
"col": [ |
|||
"hope", "eve", "abi", "dee", "bea", |
|||
"fay", "ivy", "gay", "cath", "jan"], |
|||
"dan": [ |
|||
"ivy", "fay", "dee", "gay", "hope", |
|||
"eve", "jan", "bea", "cath", "abi"], |
|||
"ed": [ |
|||
"jan", "dee", "bea", "cath", "fay", |
|||
"eve", "abi", "ivy", "hope", "gay"], |
|||
"fred": [ |
|||
"bea", "abi", "dee", "gay", "eve", |
|||
"ivy", "cath", "jan", "hope", "fay"], |
|||
"gav": [ |
|||
"gay", "eve", "ivy", "bea", "cath", |
|||
"abi", "dee", "hope", "jan", "fay"], |
|||
"hal": [ |
|||
"abi", "eve", "hope", "fay", "ivy", |
|||
"cath", "jan", "bea", "gay", "dee"], |
|||
"ian": [ |
|||
"hope", "cath", "dee", "gay", "bea", |
|||
"abi", "fay", "ivy", "jan", "eve"], |
|||
"jon": [ |
|||
"abi", "fay", "jan", "gay", "eve", |
|||
"bea", "dee", "cath", "ivy", "hope"] |
|||
} |
|||
var wPref = { |
|||
"abi": { |
|||
"bob": 1, "fred": 2, "jon": 3, "gav": 4, "ian": 5, |
|||
"abe": 6, "dan": 7, "ed": 8, "col": 9, "hal": 10}, |
|||
"bea": { |
|||
"bob": 1, "abe": 2, "col": 3, "fred": 4, "gav": 5, |
|||
"dan": 6, "ian": 7, "ed": 8, "jon": 9, "hal": 10}, |
|||
"cath": { |
|||
"fred": 1, "bob": 2, "ed": 3, "gav": 4, "hal": 5, |
|||
"col": 6, "ian": 7, "abe": 8, "dan": 9, "jon": 10}, |
|||
"dee": { |
|||
"fred": 1, "jon": 2, "col": 3, "abe": 4, "ian": 5, |
|||
"hal": 6, "gav": 7, "dan": 8, "bob": 9, "ed": 10}, |
|||
"eve": { |
|||
"jon": 1, "hal": 2, "fred": 3, "dan": 4, "abe": 5, |
|||
"gav": 6, "col": 7, "ed": 8, "ian": 9, "bob": 10}, |
|||
"fay": { |
|||
"bob": 1, "abe": 2, "ed": 3, "ian": 4, "jon": 5, |
|||
"dan": 6, "fred": 7, "gav": 8, "col": 9, "hal": 10}, |
|||
"gay": { |
|||
"jon": 1, "gav": 2, "hal": 3, "fred": 4, "bob": 5, |
|||
"abe": 6, "col": 7, "ed": 8, "dan": 9, "ian": 10}, |
|||
"hope": { |
|||
"gav": 1, "jon": 2, "bob": 3, "abe": 4, "ian": 5, |
|||
"dan": 6, "hal": 7, "ed": 8, "col": 9, "fred": 10}, |
|||
"ivy": { |
|||
"ian": 1, "col": 2, "hal": 3, "gav": 4, "fred": 5, |
|||
"bob": 6, "abe": 7, "ed": 8, "jon": 9, "dan": 10}, |
|||
"jan": { |
|||
"ed": 1, "hal": 2, "gav": 3, "abe": 4, "bob": 5, |
|||
"jon": 6, "col": 7, "ian": 8, "fred": 9, "dan": 10} |
|||
} |
|||
// Pair implements the Gale/Shapely algorithm. |
|||
var pair = Fn.new { |pPref, rPref| |
|||
// code is destructive on the maps, so work with copies |
|||
var pFree = {} |
|||
for (me in pPref) pFree[me.key] = me.value |
|||
var rFree = {} |
|||
for (me in rPref) rFree[me.key] = me.value |
|||
// struct only used in this function. |
|||
// preferences must be saved in case engagement is broken. |
|||
var Save = Struct.create("Save", ["proposer", "pPref", "rPref"]) |
|||
var proposals = {} // key is recipient (w) |
|||
// WP pseudocode comments prefaced with WP: m is proposer, w is recipient. |
|||
// WP: while ∃ free man m who still has a woman w to propose to |
|||
while (pFree.count > 0) { // while there is a free proposer, |
|||
var proposer |
|||
var ppref |
|||
for (me in pFree) { |
|||
proposer = me.key |
|||
ppref = me.value |
|||
break // pick a proposer at random, whatever map iteration delivers first. |
|||
} |
|||
if (ppref.count == 0) continue // if proposer has no possible recipients, skip |
|||
// WP: w = m's highest ranked such woman to whom he has not yet proposed |
|||
var recipient = ppref[0] // highest ranged is first in list. |
|||
ppref = ppref[1..-1] // pop from list |
|||
var rpref = {} |
|||
// WP: if w is free |
|||
if (rpref = rFree[recipient]) { |
|||
// WP: (m, w) become engaged |
|||
// (common code follows if statement) |
|||
} else { |
|||
// WP: else some pair (m', w) already exists |
|||
var s = proposals[recipient] // get proposal saved preferences |
|||
// WP: if w prefers m to m' |
|||
if (s.rPref[proposer] < s.rPref[s.proposer]) { |
|||
System.print("engagement broken: %(recipient) %(s.proposer)") |
|||
// WP: m' becomes free |
|||
pFree[s.proposer] = s.pPref // return proposer to the map |
|||
// WP: (m, w) become engaged |
|||
rpref = s.rPref |
|||
// (common code follows if statement) |
|||
} else { |
|||
// WP: else (m', w) remain engaged |
|||
pFree[proposer] = ppref // update preferences in map |
|||
continue |
|||
} |
|||
} |
|||
System.print("engagement: %(recipient) %(proposer)") |
|||
proposals[recipient] = Save.new(proposer, ppref, rpref) |
|||
pFree.remove(proposer) |
|||
rFree.remove(recipient) |
|||
} |
|||
// construct return value |
|||
var ps = {} |
|||
for (me in proposals) { |
|||
ps[me.key] = me.value.proposer |
|||
} |
|||
return ps |
|||
} |
|||
var validateStable = Fn.new { |ps, pPref, rPref| |
|||
for (me in ps) System.print("%(me.key) %(me.value)") |
|||
for (me in ps) { |
|||
var r = me.key |
|||
var p = me.value |
|||
for (rp in pPref[p]) { |
|||
if (rp == r) break |
|||
var rprefs = rPref[rp] |
|||
if (rprefs[p] < rprefs[ps[rp]]) { |
|||
System.print("unstable.") |
|||
System.print("%(p) and %(rp) would prefer each other over their current pairings.") |
|||
return false |
|||
} |
|||
} |
|||
} |
|||
System.print("stable.") |
|||
return true |
|||
} |
|||
// get parings by Gale/Shapley algorithm |
|||
var ps = pair.call(mPref, wPref) |
|||
// show results |
|||
System.print("\nresult:") |
|||
if (!validateStable.call(ps, mPref, wPref)) return |
|||
// perturb |
|||
while (true) { |
|||
var i = 0 |
|||
var w2 = List.filled(2, null) |
|||
var m2 = List.filled(2, null) |
|||
for (me in ps) { |
|||
w2[i] = me.key |
|||
m2[i] = me.value |
|||
if (i == 1) break |
|||
i = i + 1 |
|||
} |
|||
System.print("\nexchanging partners of %(m2[0]) and %(m2[1])") |
|||
ps[w2[0]] = m2[1] |
|||
ps[w2[1]] = m2[0] |
|||
// validate perturbed parings |
|||
if (!validateStable.call(ps, mPref, wPref)) return |
|||
// if those happened to be stable as well, perturb more |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
engagement: hope col |
|||
engagement broken: hope col |
|||
engagement: hope ian |
|||
engagement: eve col |
|||
engagement: cath bob |
|||
engagement: ivy dan |
|||
engagement: bea fred |
|||
engagement: gay gav |
|||
engagement: abi hal |
|||
engagement: jan ed |
|||
engagement broken: abi hal |
|||
engagement: abi abe |
|||
engagement broken: eve col |
|||
engagement: eve hal |
|||
engagement: dee col |
|||
engagement broken: abi abe |
|||
engagement: abi jon |
|||
engagement broken: ivy dan |
|||
engagement: ivy abe |
|||
engagement: fay dan |
|||
result: |
|||
bea fred |
|||
gay gav |
|||
eve hal |
|||
dee col |
|||
hope ian |
|||
fay dan |
|||
abi jon |
|||
cath bob |
|||
ivy abe |
|||
jan ed |
|||
stable. |
|||
exchanging partners of fred and gav |
|||
bea gav |
|||
gay fred |
|||
eve hal |
|||
dee col |
|||
hope ian |
|||
fay dan |
|||
abi jon |
|||
cath bob |
|||
ivy abe |
|||
jan ed |
|||
unstable. |
|||
gav and gay would prefer each other over their current pairings. |
|||
</pre> |
</pre> |
||