Stable marriage problem

Solve the Stable marriage problem using the Gale Shapley algorithm.

Task Specifics
Given ten males:

   abe, bob, col, dan, ed, fred, gav, hal, ian, jon

And ten females:

   abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan

And a complete list of ranked preferences, where the most liked is to the left:

  abe: abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay
  bob: cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay
  col: hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan
  dan: ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi
   ed: jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay
 fred: bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay
  gav: gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay
  hal: abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee
  ian: hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve
  jon: abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope
   
  abi: bob, fred, jon, gav, ian, abe, dan, ed, col, hal
  bea: bob, abe, col, fred, gav, dan, ian, ed, jon, hal
 cath: fred, bob, ed, gav, hal, col, ian, abe, dan, jon
  dee: fred, jon, col, abe, ian, hal, gav, dan, bob, ed
  eve: jon, hal, fred, dan, abe, gav, col, ed, ian, bob
  fay: bob, abe, ed, ian, jon, dan, fred, gav, col, hal
  gay: jon, gav, hal, fred, bob, abe, col, ed, dan, ian
 hope: gav, jon, bob, abe, ian, dan, hal, ed, col, fred
  ivy: ian, col, hal, gav, fred, bob, abe, ed, jon, dan
  jan: ed, hal, gav, abe, bob, jon, col, ian, fred, dan

Use the Gale Shapley algorithm to find a stable set of engagements
Perturb this set of engagements to form an unstable set of engagements then check this new set for stability.

Reference

The Stable Marriage Problem. (Eloquent description and background information).

Python

<lang python>import random, 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'],

'bob': ['cath', 'hope', 'abi', 'dee', 'eve', 'fay', 'bea', 'jan', 'ivy', 'gay'],
'col': ['hope', 'eve', 'abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan'],
'dan': ['ivy', 'fay', 'dee', 'gay', 'hope', 'eve', 'jan', 'bea', 'cath', 'abi'],
'ed': ['jan', 'dee', 'bea', 'cath', 'fay', 'eve', 'abi', 'ivy', 'hope', 'gay'],
'fred': ['bea', 'abi', 'dee', 'gay', 'eve', 'ivy', 'cath', 'jan', 'hope', 'fay'],
'gav': ['gay', 'eve', 'ivy', 'bea', 'cath', 'abi', 'dee', 'hope', 'jan', 'fay'],
'hal': ['abi', 'eve', 'hope', 'fay', 'ivy', 'cath', 'jan', 'bea', 'gay', 'dee'],
'ian': ['hope', 'cath', 'dee', 'gay', 'bea', 'abi', 'fay', 'ivy', 'jan', 'eve'],
'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'],
'cath': ['fred', 'bob', 'ed', 'gav', 'hal', 'col', 'ian', 'abe', 'dan', 'jon'],
'dee': ['fred', 'jon', 'col', 'abe', 'ian', 'hal', 'gav', 'dan', 'bob', 'ed'],
'eve': ['jon', 'hal', 'fred', 'dan', 'abe', 'gav', 'col', 'ed', 'ian', 'bob'],
'fay': ['bob', 'abe', 'ed', 'ian', 'jon', 'dan', 'fred', 'gav', 'col', 'hal'],
'gay': ['jon', 'gav', 'hal', 'fred', 'bob', 'abe', 'col', 'ed', 'dan', 'ian'],
'hope': ['gav', 'jon', 'bob', 'abe', 'ian', 'dan', 'hal', 'ed', 'col', 'fred'],
'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]
       shelikesbetter = shelikes[0:shelikes.index(he)]
       helikes = guyprefers[he]
       helikesbetter = helikes[0:helikes.index(she)]
       for guy in shelikesbetter:
           guysgirl = inverseengaged[guy]
           guylikes = guyprefers[guy]
           if guylikes.index(guysgirl) > guylikes.index(she):
               print("%s likes %s better than %s and %s likes %s better than their current partner"
                     % (she, guy, he, guy, she))
               return False
       for gal in helikesbetter:
           girlsguy = engaged[gal]
           gallikes = galprefers[gal]
           if gallikes.index(girlsguy) > gallikes.index(he):
               print("%s likes %s better than %s and %s likes %s better than their current partner"
                     % (he, gal, she, gal, he))
               return False
   return True

def matchmaker():

   guysfree = guys[:]
   engaged  = defaultdict(str)
   guyprefers2 = copy.deepcopy(guyprefers)
   galprefers2 = copy.deepcopy(galprefers)
   while guysfree:
       guy = guysfree.pop(0)
       guyslist = guyprefers2[guy]
       gal = guyslist.pop(0)
       fiance = engaged[gal]
       if not fiance:
           # She's free
           engaged[gal] = guy
           print("  %s and %s" % (guy, gal))
       else:
           # The bounder proposes to an engaged lass!
           galslist = galprefers2[gal]
           if galslist.index(fiance) > galslist.index(guy):
               # She prefers new guy
               engaged[gal] = guy
               print("  %s dumped %s for %s" % (gal, fiance, guy))
               if guyprefers2[fiance]:
                   # Ex has more girls to try
                   guysfree.append(fiance)
           else:
               # She is fsithful 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

                         for couple in sorted(engaged.items())))

print() 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]] for gal in gals[:2]:

   print('  %s is now engaged to %s' % (gal, engaged[gal]))

print() print('Engagement stability check PASSED'

     if check(engaged) else 'Engagement stability check FAILED')</lang>

Sample Output

Engagements:
  abe and abi
  bob and cath
  col and hope
  dan and ivy
  ed and jan
  fred and bea
  gav and gay
  hope dumped col for ian
  abi dumped abe for jon
  hal and eve
  col and dee
  ivy dumped dan for abe
  dan and fay

Couples:
  abi is engaged to jon,
  bea is engaged to fred,
  cath is engaged to bob,
  dee is engaged to col,
  eve is engaged to hal,
  fay is engaged to dan,
  gay is engaged to gav,
  hope is engaged to ian,
  ivy is engaged to abe,
  jan is engaged to ed

Engagement stability check PASSED


Swapping two fiances to introduce an error
  abi is now engaged to fred
  bea is now engaged to jon

fay likes jon better than dan and jon likes fay better than their current partner
Engagement stability check FAILED