Stable marriage problem: Difference between revisions
Content deleted Content added
m →{{header|Python}}: Shortened lines |
|||
Line 678: | Line 678: | ||
<lang python>import copy |
<lang python>import copy |
||
from collections import defaultdict |
from collections import defaultdict |
||
guys = 'abe bob col dan ed fred gav hal ian jon'.strip().split() |
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() |
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'], |
|||
'bob': ['cath', 'hope', 'abi', 'dee', 'eve', 'fay', 'bea', 'jan', 'ivy', 'gay'], |
'bob': ['cath', 'hope', 'abi', 'dee', 'eve', 'fay', 'bea', 'jan', 'ivy', 'gay'], |
||
'col': ['hope', 'eve', 'abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan'], |
'col': ['hope', 'eve', 'abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan'], |
||
Line 692: | Line 693: | ||
'ian': ['hope', 'cath', 'dee', 'gay', 'bea', 'abi', 'fay', 'ivy', 'jan', 'eve'], |
'ian': ['hope', 'cath', 'dee', 'gay', 'bea', 'abi', 'fay', 'ivy', 'jan', 'eve'], |
||
'jon': ['abi', 'fay', 'jan', 'gay', 'eve', 'bea', 'dee', 'cath', 'ivy', 'hope']} |
'jon': ['abi', 'fay', 'jan', 'gay', 'eve', 'bea', 'dee', 'cath', 'ivy', 'hope']} |
||
galprefers = { |
|||
'abi': ['bob', 'fred', 'jon', 'gav', 'ian', 'abe', 'dan', 'ed', 'col', 'hal'], |
|||
'bea': ['bob', 'abe', 'col', 'fred', 'gav', 'dan', 'ian', 'ed', 'jon', 'hal'], |
'bea': ['bob', 'abe', 'col', 'fred', 'gav', 'dan', 'ian', 'ed', 'jon', 'hal'], |
||
'cath': ['fred', 'bob', 'ed', 'gav', 'hal', 'col', 'ian', 'abe', 'dan', 'jon'], |
'cath': ['fred', 'bob', 'ed', 'gav', 'hal', 'col', 'ian', 'abe', 'dan', 'jon'], |
||
Line 702: | Line 704: | ||
'ivy': ['ian', 'col', 'hal', 'gav', 'fred', 'bob', 'abe', 'ed', 'jon', 'dan'], |
'ivy': ['ian', 'col', 'hal', 'gav', 'fred', 'bob', 'abe', 'ed', 'jon', 'dan'], |
||
'jan': ['ed', 'hal', 'gav', 'abe', 'bob', 'jon', 'col', 'ian', 'fred', 'dan']} |
'jan': ['ed', 'hal', 'gav', 'abe', 'bob', 'jon', 'col', 'ian', 'fred', 'dan']} |
||
def check(engaged): |
def check(engaged): |
||
inverseengaged = dict((v,k) for k,v in engaged.items()) |
inverseengaged = dict((v,k) for k,v in engaged.items()) |
||
Line 715: | Line 717: | ||
guylikes = guyprefers[guy] |
guylikes = guyprefers[guy] |
||
if guylikes.index(guysgirl) > guylikes.index(she): |
if guylikes.index(guysgirl) > guylikes.index(she): |
||
print("%s likes %s better than %s and %s likes %s better than |
print("%s likes %s better than %s and %s likes %s better than " |
||
"their current partner" |
|||
% (she, guy, he, guy, she)) |
% (she, guy, he, guy, she)) |
||
return False |
return False |
||
Line 722: | Line 725: | ||
gallikes = galprefers[gal] |
gallikes = galprefers[gal] |
||
if gallikes.index(girlsguy) > gallikes.index(he): |
if gallikes.index(girlsguy) > gallikes.index(he): |
||
print("%s likes %s better than %s and %s likes %s better than |
print("%s likes %s better than %s and %s likes %s better than " |
||
"their current partner" |
|||
% (he, gal, she, gal, he)) |
% (he, gal, she, gal, he)) |
||
return False |
return False |
||
return True |
return True |
||
def matchmaker(): |
def matchmaker(): |
||
guysfree = guys[:] |
guysfree = guys[:] |
||
Line 757: | Line 761: | ||
guysfree.append(guy) |
guysfree.append(guy) |
||
return engaged |
return engaged |
||
print('\nEngagements:') |
print('\nEngagements:') |
||
engaged = matchmaker() |
engaged = matchmaker() |
||
print('\nCouples:') |
print('\nCouples:') |
||
print(' ' + ',\n '.join('%s is engaged to %s' % couple |
print(' ' + ',\n '.join('%s is engaged to %s' % couple |
||
Line 768: | Line 772: | ||
print('Engagement stability check PASSED' |
print('Engagement stability check PASSED' |
||
if check(engaged) else 'Engagement stability check FAILED') |
if check(engaged) else 'Engagement stability check FAILED') |
||
print('\n\nSwapping two fiances to introduce an error') |
print('\n\nSwapping two fiances to introduce an error') |
||
engaged[gals[0]], engaged[gals[1]] = engaged[gals[1]], engaged[gals[0]] |
engaged[gals[0]], engaged[gals[1]] = engaged[gals[1]], engaged[gals[0]] |