Stable marriage problem: Difference between revisions
Added 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 52:
# [http://www.ams.org/samplings/feature-column/fc-2015-03 The Stable Marriage Problem and School Choice]. (Excellent exposition)
<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}}==
| |||