Stable marriage problem: Difference between revisions
Content added Content deleted
(→{{header|OCaml}}: Marked incorrect as no output is shown.) |
(J Implementation) |
||
Line 334: | Line 334: | ||
Marriages are unstable, e.g.: |
Marriages are unstable, e.g.: |
||
bea and fred like each other better than their current partners abi and jon</lang> |
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}}== |
=={{header|Java}}== |
||
Line 536: | Line 649: | ||
fred likes bea better than abi and bea likes fred better than their current partner |
fred likes bea better than abi and bea likes fred better than their current partner |
||
Marriages are unstable</pre> |
Marriages are unstable</pre> |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |