Stable marriage problem: Difference between revisions
Added Wren
(Add Nim solution) |
(Added Wren) |
||
Line 7,799:
ian - hope
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>
| |||