Stable marriage problem: Difference between revisions
J Implementation
(→{{header|OCaml}}: Marked incorrect as no output is shown.) |
(J Implementation) |
||
Line 334:
Marriages are unstable, e.g.:
bea and fred like each other better than their current partners abi and jon</lang>
=={{header|J}}==
<lang j>mraw=:;:;._2]0 :0-.':,'
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
)
fraw=:;:;._2]0 :0-.':,'
abi: bob, fred, jon, gav, ian, abe, dan, ed, col, hal
bea: bob, abe, col, fred, gav, dan, ian, ed, jon, hal
cath: fred, bob, ed, gav, hal, col, ian, abe, dan, jon
dee: fred, jon, col, abe, ian, hal, gav, dan, bob, ed
eve: jon, hal, fred, dan, abe, gav, col, ed, ian, bob
fay: bob, abe, ed, ian, jon, dan, fred, gav, col, hal
gay: jon, gav, hal, fred, bob, abe, col, ed, dan, ian
hope: gav, jon, bob, abe, ian, dan, hal, ed, col, fred
ivy: ian, col, hal, gav, fred, bob, abe, ed, jon, dan
jan: ed, hal, gav, abe, bob, jon, col, ian, fred, dan
)
male=:{."1 mraw
feml=:{."1 fraw
mpref=:feml i.(}."1 mraw)
fpref=:male i.(}."1 fraw)
init=:(,:%)_"0 male NB. initial state: all males unengaged
propose=:4 :0
'engaged etc'=.x
'male feml'=.y
if.feml e. engaged do.
pref=.feml{fpref
fiance=. engaged i.feml
if. male <&(pref&i.) fiance do.
engaged=. feml male} _ fiance} engaged
end.
else.
engaged=. feml male} engaged
end.
engaged,:etc
)
GaleShap=:3 :0
whilst._ e.{.y do.
for_guy.I._={.y do.
ctrl=. <1,guy
next=. ctrl{y
gal=. (<guy,next){mpref
y=. y propose guy,gal
y=. (next+1) ctrl} y
end.
end.
male,:({.y){feml
)
Stable=:3 :0
guy=.male i.{.y
gal=.feml i.{:y
satisfied=. ] >: (<0 1) |: ]
mhappy=. satisfied (guy{mpref) i."1 0/ gal
fhappy=. satisfied (gal{fpref) i."1 0/ guy
stable=. mhappy+.|:fhappy
if.bad=.0 e.,stable do.
smoutput 'Better matches:'
smoutput ((guy{male),:(gal{feml)){~"1 0"2 1($stable)#:I.,-.stable
end.
assert-.bad
)
</lang>
Example use:
<lang> GaleShap init
┌───┬────┬───┬───┬───┬────┬───┬───┬────┬───┐
│abe│bob │col│dan│ed │fred│gav│hal│ian │jon│
├───┼────┼───┼───┼───┼────┼───┼───┼────┼───┤
│ivy│cath│dee│fay│jan│bea │gay│eve│hope│abi│
└───┴────┴───┴───┴───┴────┴───┴───┴────┴───┘</lang>
Stability check:
<lang j> 1 2 A."_1 GaleShap init NB. perturbed matches
┌───┬────┬───┬───┬───┬────┬───┬────┬───┬───┐
│abe│bob │col│dan│ed │fred│gav│hal │jon│ian│
├───┼────┼───┼───┼───┼────┼───┼────┼───┼───┤
│ivy│cath│dee│fay│jan│bea │gay│hope│eve│abi│
└───┴────┴───┴───┴───┴────┴───┴────┴───┴───┘
Stable 1 2 A."_1 GaleShap init
Better matches:
┌───┬────┐
│jon│fay │
├───┼────┤
│jon│gay │
├───┼────┤
│jon│abi │
├───┼────┤
│ian│hope│
└───┴────┘
|assertion failure: assert
| assert-.bad</lang>
As an aside, note that the guys fared much better than the gals here, with over half of the guys getting their first preference and only one gal getting her first preference. The worst matching for any guy was fourth preference where the worst for any gal was seventh preference.
=={{header|Java}}==
Line 536 ⟶ 649:
fred likes bea better than abi and bea likes fred better than their current partner
Marriages are unstable</pre>
=={{header|OCaml}}==
| |||