Stable marriage problem: Difference between revisions

Line 678:

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

guyprefers = {

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

Line 704:

Line 701:

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

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

guys = sorted(guyprefers.keys())

gals = sorted(galprefers.keys())

def check(engaged):

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

for she, he in engaged.items():

shelikes = galprefers[she]

shelikesbetter = shelikes[0:shelikes.index(he)]

shelikesbetter = shelikes[:shelikes.index(he)]

helikes = guyprefers[he]

helikesbetter = helikes[0:helikes.index(she)]

helikesbetter = helikes[:helikes.index(she)]

for guy in shelikesbetter:

guysgirl = inverseengaged[guy]

Line 730:

return False

return True

def matchmaker():

guysfree = guys[:]

Line 756:

guysfree.append(fiance)

else:

# She is ~~fsithful~~ to old fiance

# She is faithful to old fiance

if guyslist:

# Look again

guysfree.append(guy)

return engaged

print('\nEngagements:')

engaged = matchmaker()

print('\nCouples:')

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

Line 772:

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