Stable marriage problem: Difference between revisions

<lang python>import copy

from collections import defaultdict

guyprefers = {

'abe': ['abi', 'eve', 'cath', 'ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay'],

'ivy': ['ian', 'col', 'hal', 'gav', 'fred', 'bob', 'abe', 'ed', 'jon', 'dan'],

'jan': ['ed', 'hal', 'gav', 'abe', 'bob', 'jon', 'col', 'ian', 'fred', 'dan']}

def check(engaged):

inverseengaged = dict((v,k) for k,v in engaged.items())

for she, he in engaged.items():

shelikes = galprefers[she]

helikes = guyprefers[he]

for guy in shelikesbetter:

guysgirl = inverseengaged[guy]

return False

return True

def matchmaker():

guysfree = guys[:]

guysfree.append(fiance)

else:

if guyslist:

# Look again

guysfree.append(guy)

return engaged

print('\nEngagements:')

engaged = matchmaker()

print('\nCouples:')

print(' ' + ',\n '.join('%s is engaged to %s' % couple

print('Engagement stability check PASSED'

if check(engaged) else 'Engagement stability check FAILED')

print('\n\nSwapping two fiances to introduce an error')

engaged[gals[0]], engaged[gals[1]] = engaged[gals[1]], engaged[gals[0]]