Stable marriage problem: Difference between revisions

=={{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>