Stable marriage problem: Difference between revisions

<lang python>import copy

from collections import defaultdict

guys = 'abe bob col dan ed fred gav hal ian jon'.strip().split()

gals = 'abi bea cath dee eve fay gay hope ivy jan'.strip().split()

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

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

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

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

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

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

'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())

guylikes = guyprefers[guy]

if guylikes.index(guysgirl) > guylikes.index(she):

% (she, guy, he, guy, she))

return False

gallikes = galprefers[gal]

if gallikes.index(girlsguy) > gallikes.index(he):

% (he, gal, she, gal, he))

return False

return True

def matchmaker():

guysfree = guys[:]

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]]