Stable marriage problem: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 52: | Line 52: | ||
# [http://www.ams.org/samplings/feature-column/fc-2015-03 The Stable Marriage Problem and School Choice]. (Excellent exposition) |
# [http://www.ams.org/samplings/feature-column/fc-2015-03 The Stable Marriage Problem and School Choice]. (Excellent exposition) |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<lang 11l>V guyprefers = [‘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’]] |
|||
V galprefers = [‘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’]] |
|||
V guys = sorted(guyprefers.keys()) |
|||
V gals = sorted(galprefers.keys()) |
|||
F check(engaged) |
|||
V inverseengaged = Dict(engaged.map((k, v) -> (v, k))) |
|||
L(she, he) engaged |
|||
V shelikes = :galprefers[she] |
|||
V shelikesbetter = shelikes[0 .< shelikes.index(he)] |
|||
V helikes = :guyprefers[he] |
|||
V helikesbetter = helikes[0 .< helikes.index(she)] |
|||
L(guy) shelikesbetter |
|||
V guysgirl = inverseengaged[guy] |
|||
V guylikes = :guyprefers[guy] |
|||
I guylikes.index(guysgirl) > guylikes.index(she) |
|||
print(‘#. and #. like each other better than their present partners: #. and #., respectively’.format(she, guy, he, guysgirl)) |
|||
R 0B |
|||
L(gal) helikesbetter |
|||
V girlsguy = engaged[gal] |
|||
V gallikes = :galprefers[gal] |
|||
I gallikes.index(girlsguy) > gallikes.index(he) |
|||
print(‘#. and #. like each other better than their present partners: #. and #., respectively’.format(he, gal, she, girlsguy)) |
|||
R 0B |
|||
R 1B |
|||
F matchmaker() |
|||
V guysfree = copy(:guys) |
|||
[String = String] engaged |
|||
V guyprefers2 = copy(:guyprefers) |
|||
V galprefers2 = copy(:galprefers) |
|||
L !guysfree.empty |
|||
V guy = guysfree.pop(0) |
|||
V& guyslist = guyprefers2[guy] |
|||
V gal = guyslist.pop(0) |
|||
V fiance = engaged.get(gal, ‘’) |
|||
I fiance == ‘’ |
|||
engaged[gal] = guy |
|||
print(‘ #. and #.’.format(guy, gal)) |
|||
E |
|||
V galslist = galprefers2[gal] |
|||
I galslist.index(fiance) > galslist.index(guy) |
|||
engaged[gal] = guy |
|||
print(‘ #. dumped #. for #.’.format(gal, fiance, guy)) |
|||
I !guyprefers2[fiance].empty |
|||
guysfree.append(fiance) |
|||
E |
|||
I !guyslist.empty |
|||
guysfree.append(guy) |
|||
R engaged |
|||
print("\nEngagements:") |
|||
V engaged = matchmaker() |
|||
print("\nCouples:") |
|||
print(‘ ’sorted(engaged.items()).map((couple_key, couple_val) -> ‘#. is engaged to #.’.format(couple_key, couple_val)).join(",\n ")) |
|||
print() |
|||
print(I check(engaged) {‘Engagement stability check PASSED’} E ‘Engagement stability check FAILED’) |
|||
print("\n\nSwapping two fiances to introduce an error") |
|||
swap(&engaged[gals[0]], &engaged[gals[1]]) |
|||
L(gal) gals[0.<2] |
|||
print(‘ #. is now engaged to #.’.format(gal, engaged[gal])) |
|||
print() |
|||
print(I check(engaged) {‘Engagement stability check PASSED’} E ‘Engagement stability check FAILED’)</lang> |
|||
{{out}} |
|||
<pre> |
|||
Engagements: |
|||
abe and abi |
|||
bob and cath |
|||
col and hope |
|||
dan and ivy |
|||
ed and jan |
|||
fred and bea |
|||
gav and gay |
|||
hope dumped col for ian |
|||
abi dumped abe for jon |
|||
hal and eve |
|||
col and dee |
|||
ivy dumped dan for abe |
|||
dan and fay |
|||
Couples: |
|||
abi is engaged to jon, |
|||
bea is engaged to fred, |
|||
cath is engaged to bob, |
|||
dee is engaged to col, |
|||
eve is engaged to hal, |
|||
fay is engaged to dan, |
|||
gay is engaged to gav, |
|||
hope is engaged to ian, |
|||
ivy is engaged to abe, |
|||
jan is engaged to ed |
|||
Engagement stability check PASSED |
|||
Swapping two fiances to introduce an error |
|||
abi is now engaged to fred |
|||
bea is now engaged to jon |
|||
fred and bea like each other better than their present partners: abi and jon, respectively |
|||
Engagement stability check FAILED |
|||
</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |