Stable marriage problem: Difference between revisions
Content deleted Content added
m →{{header|Python}}: Shortened lines |
|||
Line 678:
<lang python>import copy
from collections import defaultdict
guyprefers = {
'abe': ['abi', 'eve', 'cath', 'ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay'],
Line 704 ⟶ 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[
helikes = guyprefers[he]
helikesbetter = helikes[
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
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]]
|