Stable marriage problem

From Rosetta Code
(Redirected from Gale-Shapley algorithm)
Task
Stable marriage problem
You are encouraged to solve this task according to the task description, using any language you may know.

Solve the Stable marriage problem using the Gale/Shapley algorithm.


Problem description
Given an equal number of men and women to be paired for marriage, each man ranks all the women in order of his preference and each woman ranks all the men in order of her preference.

A stable set of engagements for marriage is one where no man prefers a woman over the one he is engaged to, where that other woman also prefers that man over the one she is engaged to. I.e. with consulting marriages, there would be no reason for the engagements between the people to change.

Gale and Shapley proved that there is a stable set of engagements for any set of preferences and the first link above gives their algorithm for finding a set of stable engagements.


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
  1. Use the Gale Shapley algorithm to find a stable set of engagements
  2. Perturb this set of engagements to form an unstable set of engagements then check this new set for stability.


References

  1. The Stable Marriage Problem. (Eloquent description and background information).
  2. Gale-Shapley Algorithm Demonstration.
  3. Another Gale-Shapley Algorithm Demonstration.
  4. Stable Marriage Problem - Numberphile (Video).
  5. Stable Marriage Problem (the math bit) (Video).
  6. The Stable Marriage Problem and School Choice. (Excellent exposition)



11l[edit]

Translation of: Python
V 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’]]
V 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’]]

V guys = sorted(guyprefers.keys())
V gals = sorted(galprefers.keys())

F check(engaged)
   V inverseengaged = Dict(engaged.map((k, v) -> (v, k)))
   L(she, he) engaged
      V shelikes = :galprefers[she]
      V shelikesbetter = shelikes[0 .< shelikes.index(he)]
      V helikes = :guyprefers[he]
      V helikesbetter = helikes[0 .< helikes.index(she)]
      L(guy) shelikesbetter
         V guysgirl = inverseengaged[guy]
         V guylikes = :guyprefers[guy]
         I guylikes.index(guysgirl) > guylikes.index(she)
            print(‘#. and #. like each other better than their present partners: #. and #., respectively’.format(she, guy, he, guysgirl))
            R 0B
      L(gal) helikesbetter
         V girlsguy = engaged[gal]
         V gallikes = :galprefers[gal]
         I gallikes.index(girlsguy) > gallikes.index(he)
            print(‘#. and #. like each other better than their present partners: #. and #., respectively’.format(he, gal, she, girlsguy))
            R 0B
   R 1B

F matchmaker()
   V guysfree = copy(:guys)
   [String = String] engaged
   V guyprefers2 = copy(:guyprefers)
   V galprefers2 = copy(:galprefers)
   L !guysfree.empty
      V guy = guysfree.pop(0)
      V& guyslist = guyprefers2[guy]
      V gal = guyslist.pop(0)
      V fiance = engaged.get(gal, ‘’)
      I fiance == ‘’
         engaged[gal] = guy
         print(‘  #. and #.’.format(guy, gal))
      E
         V galslist = galprefers2[gal]
         I galslist.index(fiance) > galslist.index(guy)
            engaged[gal] = guy
            print(‘  #. dumped #. for #.’.format(gal, fiance, guy))
            I !guyprefers2[fiance].empty
               guysfree.append(fiance)
         E
            I !guyslist.empty
               guysfree.append(guy)
   R engaged

print("\nEngagements:")
V engaged = matchmaker()

print("\nCouples:")
print(‘  ’sorted(engaged.items()).map((couple_key, couple_val) -> ‘#. is engaged to #.’.format(couple_key, couple_val)).join(",\n  "))
print()
print(I check(engaged) {‘Engagement stability check PASSED’} E ‘Engagement stability check FAILED’)

print("\n\nSwapping two fiances to introduce an error")
swap(&engaged[gals[0]], &engaged[gals[1]])
L(gal) gals[0.<2]
   print(‘  #. is now engaged to #.’.format(gal, engaged[gal]))
print()
print(I check(engaged) {‘Engagement stability check PASSED’} E ‘Engagement stability check FAILED’)
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

fred and bea like each other better than their present partners: abi and jon, respectively
Engagement stability check FAILED

AutoHotkey[edit]

Works with: AutoHotkey L
; Given 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"]

; of ten males:
males := ["abe", "bob", "col", "dan", "ed", "fred", "gav", "hal", "ian", "jon"]

; and ten females:
females := ["abi", "bea", "cath", "dee", "eve", "fay", "gay", "hope", "ivy", "jan"]

; and an empty set of engagements:
engagements := Object()
freemales := males.Clone()
,s := "Engagements:`n"

; use the Gale Shapley algorithm to find a stable set of engagements:
For i, male in freemales ; i=index of male (not needed)
{
	j:=1 ; index of female
	While (engagements[female:=%male%[j]] != "" and index(%female%, male) > index(%female%, engagements[female]))
		j++ ; each male loops through all females in order of his preference until one accepts him
	If (engagements[female] != "") ; if she was previously engaged
		freemales.insert(engagements[female]) ; her old male goes to the bottom of the list
		,s .= female . " dumped " . engagements[female] . "`n"
	engagements[female] := male ; the new engagement is registered
	,s .= female . " accepted " . male . "`n"
}

; summarize results:
s .= "`nCouples:`n"
For female, male in engagements
	s .= female . " is engaged to " . male . "`n"
s .= Stable(engagements, females)

; then perturb this set of engagements to form an unstable set of engagements then check this new set for stability:
s .= "`nWhat if cath and ivy swap?`n"
engagements["cath"]:="abe", engagements["ivy"]:="bob"
	
; summarize results:
s .= "`nCouples:`n"
For female, male in engagements
	s .= female . " is engaged to " . male . "`n"
s .= Stable(engagements, females)

Msgbox % clipboard := s
Return

; Functions:
Index(obj, value) {
	For key, val in obj
		If (val = value)
			Return, key, ErrorLevel := 0
	Return, False, Errorlevel := 1
}

Stable(engagements, females) {
	For female, male in engagements
	{
		For j, female2 in females ; j=index of female (not needed)
		{
			If (index(%male%, female) > index(%male%, female2) 
				and index(%female2%, male2:=engagements[female2]) > index(%female2%, male))
				s .= male . " is engaged to " . female . " but would prefer " . female2
					. " and " . female2 . " is engaged to " . male2 . " but would prefer " . male . "`n"
		}
	}
	If s
		Return "`nThese couples are not stable.`n" . s
	Else
		Return "`nThese couples are stable.`n"
}
Output:
Engagements:
abi accepted abe
cath accepted bob
hope accepted col
ivy accepted dan
jan accepted ed
bea accepted fred
gay accepted gav
eve accepted hal
hope dumped col
hope accepted ian
abi dumped abe
abi accepted jon
dee accepted col
ivy dumped dan
ivy accepted abe
fay accepted dan

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

These couples are stable.

What if cath and ivy swap?

Couples:
abi is engaged to jon
bea is engaged to fred
cath is engaged to abe
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 bob
jan is engaged to ed

These couples are not stable.
bob is engaged to ivy but would prefer abi and abi is engaged to jon but would prefer bob
bob is engaged to ivy but would prefer bea and bea is engaged to fred but would prefer bob
bob is engaged to ivy but would prefer cath and cath is engaged to abe but would prefer bob
bob is engaged to ivy but would prefer fay and fay is engaged to dan but would prefer bob
bob is engaged to ivy but would prefer hope and hope is engaged to ian but would prefer bob

Batch File[edit]

:: Stable Marriage Problem in Rosetta Code
:: Batch File Implementation

@echo off
setlocal enabledelayedexpansion

:: Initialization (Index Starts in 0)
set "male=abe bob col dan ed fred gav hal ian jon"
set "femm=abi bea cath dee eve fay gay hope ivy jan"

set "abe[]=abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay"
set "bob[]=cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay"
set "col[]=hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan"
set "dan[]=ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi"
set "ed[]=jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay"
set "fred[]=bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay"
set "gav[]=gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay"
set "hal[]=abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee"
set "ian[]=hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve"
set "jon[]=abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope"

set "abi[]=bob, fred, jon, gav, ian, abe, dan, ed, col, hal"
set "bea[]=bob, abe, col, fred, gav, dan, ian, ed, jon, hal"
set "cath[]=fred, bob, ed, gav, hal, col, ian, abe, dan, jon"
set "dee[]=fred, jon, col, abe, ian, hal, gav, dan, bob, ed"
set "eve[]=jon, hal, fred, dan, abe, gav, col, ed, ian, bob"
set "fay[]=bob, abe, ed, ian, jon, dan, fred, gav, col, hal"
set "gay[]=jon, gav, hal, fred, bob, abe, col, ed, dan, ian"
set "hope[]=gav, jon, bob, abe, ian, dan, hal, ed, col, fred"
set "ivy[]=ian, col, hal, gav, fred, bob, abe, ed, jon, dan"
set "jan[]=ed, hal, gav, abe, bob, jon, col, ian, fred, dan"

rem variable notation:
rem    <boy>{<index>} = <girl>
rem    <boy>[<girl>] = <index>
for %%M in (%male%) do (
   set cnt=0
   for %%. in (!%%M[]!) do (
      set "%%M{!cnt!}=%%."
      set "%%M[%%.]=!cnt!"
      set /a cnt+=1
   )
)
for %%F in (%femm%) do (
   set cnt=0
   for %%. in (!%%F[]!) do (
      set "%%F[%%.]=!cnt!"
      set /a cnt+=1
   )
)

:: The Main Thing
echo(HISTORY:
call :stableMatching
echo(
echo(NEWLYWEDS:
call :display
echo(
call :isStable
echo(
echo(What if ed and hal swapped?
call :swapper ed hal
echo(
echo(NEW-NEWLYWEDS:
call :display
echo(
call :isStable
pause>nul
exit /b 0

:: The Algorithm
:stableMatching
set "free_men=%male%"
set "free_fem=%femm%"
for %%M in (%male%) do set "%%M_tried=0"

:match_loop
if "%free_men%"=="" goto :EOF
for /f "tokens=1* delims= " %%m in ("%free_men%") do (
   rem get woman not yet proposed to, but if man's tries exceeds the number
   rem of women (poor guy), he starts again to his most preferred woman (#0).
   for /f %%x in ("!%%m_tried!") do if not defined %%m{%%x} (
      set "%%m_tried=0" & set "w=!%%m{0}!"
   ) else set "w=!%%m{%%x}!" 
   set "m=%%m"

   for /f %%x in ("free_fem:!w!=") do (
      if not "!free_fem!"=="!%%x!" (
         rem accept because !w! (the woman) is free
         set "!m!_=!w!" & set "!w!_=!m!"
         set "free_men=%%n" & set "free_fem=!%%x!"
         echo(    !w! ACCEPTED !m!.
      ) else (
         rem here, !w! already has a pair; get his name and rank.
         for /f %%. in ("!w!") do set "cur_man=!%%._!"
         for /f %%. in ("!w![!cur_man!]") do set "rank_cur=!%%.!"
         rem also, get the rank of current proposing man.
         for /f %%. in ("!w![!m!]") do set "rank_new=!%%.!"

         if !rank_new! lss !rank_cur! (
            rem here, !w! will leave her pair, and choose !m!.
            set "free_men=%%n !cur_man!"
            echo(    !w! LEFT !cur_man!.
            rem pair them up now!
            set "!m!_=!w!" & set "!w!_=!m!"
            echo(    !w! ACCEPTED !m!.
         )
      )
   )
   set /a "!m!_tried+=1"
)
goto :match_loop

:: Output the Couples
:display
for %%S in (%femm%) do echo.    %%S and !%%S_!.
goto :EOF

:: Stability Checking
:isStable
for %%f in (%femm%) do (
   for %%g in (%male%) do (
      for /f %%. in ("%%f[!%%f_!]") do set "girl_cur=!%%.!"
      set "girl_aboy=!%%f[%%g]!"
      for /f %%. in ("%%g[!%%g_!]") do set "boy_cur=!%%.!"
      set "boy_agirl=!%%g[%%f]!"

      if !boy_cur! gtr !boy_agirl! (
         if !girl_cur! gtr !girl_aboy! (
            echo(STABILITY = FALSE.
            echo(%%f and %%g would rather be together than their current partners.
            goto :EOF
         )
      )
   )
)
echo(STABILITY = TRUE.
goto :EOF

:: Swapper
:swapper
set %~1.tmp=!%~1_!
set %~2.tmp=!%~2_!
set "%~1_=!%~2.tmp!"
set "%~2_=!%~1.tmp!"
set "!%~1.tmp!_=%~2"
set "!%~2.tmp!_=%~1"
goto :EOF
Output:
HISTORY:
    abi ACCEPTED abe.
    cath ACCEPTED bob.
    hope ACCEPTED col.
    ivy ACCEPTED dan.
    jan ACCEPTED ed.
    bea ACCEPTED fred.
    gay ACCEPTED gav.
    eve ACCEPTED hal.
    hope LEFT col.
    hope ACCEPTED ian.
    abi LEFT abe.
    abi ACCEPTED jon.
    dee ACCEPTED col.
    ivy LEFT dan.
    ivy ACCEPTED abe.
    fay ACCEPTED dan.

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

STABILITY = TRUE.

What if ed and hal swapped?

NEW-NEWLYWEDS:
    abi and jon.
    bea and fred.
    cath and bob.
    dee and col.
    eve and ed.
    fay and dan.
    gay and gav.
    hope and ian.
    ivy and abe.
    jan and hal.

STABILITY = FALSE.
eve and abe would rather be together than their current partners.

BBC BASIC[edit]

      N = 10
      DIM mname$(N), wname$(N), mpref$(N), wpref$(N), mpartner%(N), wpartner%(N)
      DIM proposed&(N,N)
      mname$() = "", "Abe","Bob","Col","Dan","Ed","Fred","Gav","Hal","Ian","Jon"
      wname$() = "", "Abi","Bea","Cath","Dee","Eve","Fay","Gay","Hope","Ivy","Jan"
      mpref$() = "", "AECIJDFBHG","CHADEFBJIG","HEADBFIGCJ","IFDGHEJBCA","JDBCFEAIHG",\
      \              "BADGEICJHF","GEIBCADHJF","AEHFICJBGD","HCDGBAFIJE","AFJGEBDCIH"
      wpref$() = "", "BFJGIADECH","BACFGDIEJH","FBEGHCIADJ","FJCAIHGDBE","JHFDAGCEIB",\
      \              "BAEIJDFGCH","JGHFBACEDI","GJBAIDHECF","ICHGFBAEJD","EHGABJCIFD"
      
      REM The Gale-Shapley algorithm:
      REPEAT
        FOR m% = 1 TO N
          REPEAT
            IF mpartner%(m%) EXIT REPEAT
            FOR i% = 1 TO N
              w% = ASCMID$(mpref$(m%),i%) - 64
              IF proposed&(m%,w%) = 0 EXIT FOR
            NEXT i%
            IF i% > N EXIT REPEAT
            proposed&(m%,w%) = 1
            IF wpartner%(w%) = 0 THEN
              mpartner%(m%) = w% : REM Get engaged
              wpartner%(w%) = m%
            ELSE
              o% = wpartner%(w%)
              IF INSTR(wpref$(w%), LEFT$(mname$(m%),1)) < \
              \  INSTR(wpref$(w%), LEFT$(mname$(o%),1)) THEN
                mpartner%(o%) = 0  : REM Split up
                mpartner%(m%) = w% : REM Get engaged
                wpartner%(w%) = m%
              ENDIF
            ENDIF
          UNTIL TRUE
        NEXT m%
      UNTIL SUM(mpartner%()) = (N*(N+1))/2
      
      FOR m% = 1 TO N
        PRINT mname$(m%) " is engaged to " wname$(mpartner%(m%))
      NEXT
      PRINT "Relationships are ";
      IF FNstable PRINT "stable." ELSE PRINT "unstable."
      
      a% = RND(N)
      REPEAT b% = RND(N) : UNTIL b%<>a%
      PRINT '"Now swapping " mname$(a%) "'s and " mname$(b%) "'s partners:"
      SWAP mpartner%(a%), mpartner%(b%)
      PRINT mname$(a%) " is engaged to " wname$(mpartner%(a%))
      PRINT mname$(b%) " is engaged to " wname$(mpartner%(b%))
      PRINT "Relationships are ";
      IF FNstable PRINT "stable." ELSE PRINT "unstable."
      END
      
      DEF FNstable
      LOCAL m%, w%, o%, p%
      FOR m% = 1 TO N
        w% = mpartner%(m%)
        FOR o% = 1 TO N
          p% = wpartner%(o%)
          IF INSTR(mpref$(m%), LEFT$(wname$(o%),1)) < \
          \  INSTR(mpref$(m%), LEFT$(wname$(w%),1)) AND \
          \  INSTR(wpref$(o%), LEFT$(mname$(m%),1)) < \
          \  INSTR(wpref$(o%), LEFT$(mname$(p%),1)) THEN
            = FALSE
          ENDIF
        NEXT o%
      NEXT m%
      = TRUE

Output:

Abe is engaged to Ivy
Bob is engaged to Cath
Col is engaged to Dee
Dan is engaged to Fay
Ed is engaged to Jan
Fred is engaged to Bea
Gav is engaged to Gay
Hal is engaged to Eve
Ian is engaged to Hope
Jon is engaged to Abi
Relationships are stable.

Now swapping Hal's and Ian's partners:
Hal is engaged to Hope
Ian is engaged to Eve
Relationships are unstable.

Bracmat[edit]

(     (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)
  : ?Mplan
  : ?M
&     (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)
  : ?W
& :?engaged
&   whl
  ' (   !Mplan
      :   ?A
          (?m&~(!engaged:? (!m.?) ?).%?w ?ws)
          ( ?Z
          & (   (   ~(!engaged:?a (?m`.!w) ?z)
                  & (!m.!w) !engaged
                |   !W:? (!w.? !m ? !m` ?) ?
                  & !a (!m.!w) !z
                )
              : ?engaged
            | 
            )
          & !Z !A (!m.!ws):?Mplan
          )
    )
& ( unstable
  =   m1 m2 w1 w2
    .   !arg
      :   ?
          (?m1.?w1)
          ?
          (?m2.?w2)
          ( ?
          & (   !M:? (!m1.? !w2 ? !w1 ?) ?
              & !W:? (!w2.? !m1 ? !m2 ?) ?
            |   !M:? (!m2.? !w1 ? !w2 ?) ?
              & !W:? (!w1.? !m2 ? !m1 ?) ?
            )
          )
  )
& ( unstable$!engaged&out$unstable
  | out$stable
  )
& out$!engaged
& !engaged:(?m1.?w1) (?m2.?w2) ?others
& out$(swap !w1 for !w2)
& (   unstable$((!m1.!w2) (!m2.!w1) !others)
    & out$unstable
  | out$stable
  )
);
Output:
stable
  (dan.fay)
  (col.dee)
  (hal.eve)
  (gav.gay)
  (fred.bea)
  (ed.jan)
  (abe.ivy)
  (ian.hope)
  (bob.cath)
  (jon.abi)
swap fay for dee
unstable

C[edit]

Oddly enough (or maybe it should be that way, only that I don't know): if the women were proposing instead of the men, the resulting pairs are exactly the same.

#include <stdio.h>

int verbose = 0;
enum {
	clown = -1,
	abe, bob, col, dan, ed, fred, gav, hal, ian, jon,
	abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan,
};
const char *name[] = {
	"Abe", "Bob", "Col",  "Dan", "Ed",  "Fred", "Gav", "Hal",  "Ian", "Jon",
	"Abi", "Bea", "Cath", "Dee", "Eve", "Fay",  "Gay", "Hope", "Ivy", "Jan"
};
int pref[jan + 1][jon + 1] = {
	{ abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay },
	{ cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay },
	{ hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan },
	{ ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi },
	{ jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay },
	{ bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay },
	{ gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay },
	{ abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee },
	{ hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve },
	{ abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope },

	{ bob, fred, jon, gav, ian, abe, dan, ed, col, hal   },
	{ bob, abe, col, fred, gav, dan, ian, ed, jon, hal   },
	{ fred, bob, ed, gav, hal, col, ian, abe, dan, jon   },
	{ fred, jon, col, abe, ian, hal, gav, dan, bob, ed   },
	{ jon, hal, fred, dan, abe, gav, col, ed, ian, bob   },
	{ bob, abe, ed, ian, jon, dan, fred, gav, col, hal   },
	{ jon, gav, hal, fred, bob, abe, col, ed, dan, ian   },
	{ gav, jon, bob, abe, ian, dan, hal, ed, col, fred   },
	{ ian, col, hal, gav, fred, bob, abe, ed, jon, dan   },
	{ ed, hal, gav, abe, bob, jon, col, ian, fred, dan   },
};
int pairs[jan + 1], proposed[jan + 1];

void engage(int man, int woman)
{
	pairs[man] = woman;
	pairs[woman] = man;
	if (verbose) printf("%4s is engaged to %4s\n", name[man], name[woman]);
}

void dump(int woman, int man)
{
	pairs[man] = pairs[woman] = clown;
	if (verbose) printf("%4s dumps %4s\n", name[woman], name[man]);
}

/* how high this person ranks that: lower is more preferred */
int rank(int this, int that)
{
	int i;
	for (i = abe; i <= jon && pref[this][i] != that; i++);
	return i;
}

void propose(int man, int woman)
{
	int fiance = pairs[woman];
	if (verbose) printf("%4s proposes to %4s\n", name[man], name[woman]);

	if (fiance == clown) {
		engage(man, woman);
	} else if (rank(woman, man) < rank(woman, fiance)) {
		dump(woman, fiance);
		engage(man, woman);
	}
}

int covet(int man1, int wife2)
{
	if (rank(man1, wife2) < rank(man1, pairs[man1]) &&
			rank(wife2, man1) < rank(wife2, pairs[wife2])) {
		printf( "    %4s (w/ %4s) and %4s (w/ %4s) prefer each other"
			" over current pairing.\n",
			name[man1], name[pairs[man1]], name[wife2], name[pairs[wife2]]
		);
		return 1;
	}
	return 0;
}

int thy_neighbors_wife(int man1, int man2)
{	/* +: force checking all pairs; "||" would shortcircuit */
	return covet(man1, pairs[man2]) + covet(man2, pairs[man1]);
}

int unstable()
{
	int i, j, bad = 0;
	for (i = abe; i < jon; i++) {
		for (j = i + 1; j <= jon; j++)
			if (thy_neighbors_wife(i, j)) bad = 1;
	}
	return bad;
}

int main()
{
	int i, unengaged;
	/* init: everyone marries the clown */
	for (i = abe; i <= jan; i++)
		pairs[i] = proposed[i] = clown;

	/* rounds */
	do {
		unengaged = 0;
		for (i = abe; i <= jon; i++) {
		//for (i = abi; i <= jan; i++) { /* could let women propose */
			if (pairs[i] != clown) continue;
			unengaged = 1;
			propose(i, pref[i][++proposed[i]]);
		}
	} while (unengaged);

	printf("Pairing:\n");
	for (i = abe; i <= jon; i++)
		printf("  %4s - %s\n", name[i],
			pairs[i] == clown ? "clown" : name[pairs[i]]);

	printf(unstable()
		? "Marriages not stable\n" /* draw sad face here */
		: "Stable matchup\n");

	printf("\nBut if Bob and Fred were to swap:\n");
	i = pairs[bob];
	engage(bob, pairs[fred]);
	engage(fred, i);
	printf(unstable() ? "Marriages not stable\n" : "Stable matchup\n");

	return 0;
}
Output:
Pairing:
   Abe - Ivy
   Bob - Cath
   Col - Dee
   Dan - Fay
    Ed - Jan
  Fred - Bea
   Gav - Gay
   Hal - Eve
   Ian - Hope
   Jon - Abi
Stable matchup

But if Bob and Fred were to swap:
    Fred (w/ Cath) and  Ivy (w/  Abe) prefer each other over current pairing.
     Bob (w/  Bea) and  Fay (w/  Dan) prefer each other over current pairing.
     Bob (w/  Bea) and Hope (w/  Ian) prefer each other over current pairing.
     Bob (w/  Bea) and  Abi (w/  Jon) prefer each other over current pairing.
    Fred (w/ Cath) and  Dee (w/  Col) prefer each other over current pairing.
    Fred (w/ Cath) and  Abi (w/  Jon) prefer each other over current pairing.
Marriages not stable

C#[edit]

(This is a straight-up translation of the Objective-C version.)

using System;
using System.Collections.Generic;

namespace StableMarriage
{
    class Person
    {
        private int _candidateIndex;
        public string Name { get; set; }
        public List<Person> Prefs { get; set; }
        public Person Fiance { get; set; }
        
        public Person(string name) {
            Name = name;
            Prefs = null;
            Fiance = null;
            _candidateIndex = 0;
        }
        public bool Prefers(Person p) {
            return Prefs.FindIndex(o => o == p) < Prefs.FindIndex(o => o == Fiance);
        }
        public Person NextCandidateNotYetProposedTo() {
            if (_candidateIndex >= Prefs.Count) return null;
            return Prefs[_candidateIndex++];
        }
        public void EngageTo(Person p) {
            if (p.Fiance != null) p.Fiance.Fiance = null;
            p.Fiance = this;
            if (Fiance != null) Fiance.Fiance = null;
            Fiance = p;
        }
    }
    
    static class MainClass
    {
        static public bool IsStable(List<Person> men) {
            List<Person> women = men[0].Prefs;
            foreach (Person guy in men) {
                foreach (Person gal in women) {
                    if (guy.Prefers(gal) && gal.Prefers(guy))
                        return false;
                }
            }
            return true;
        }
        
        static void DoMarriage() {
            Person abe  = new Person("abe");
            Person bob  = new Person("bob");
            Person col  = new Person("col");
            Person dan  = new Person("dan");
            Person ed   = new Person("ed");
            Person fred = new Person("fred");
            Person gav  = new Person("gav");
            Person hal  = new Person("hal");
            Person ian  = new Person("ian");
            Person jon  = new Person("jon");
            Person abi  = new Person("abi");
            Person bea  = new Person("bea");
            Person cath = new Person("cath");
            Person dee  = new Person("dee");
            Person eve  = new Person("eve");
            Person fay  = new Person("fay");
            Person gay  = new Person("gay");
            Person hope = new Person("hope");
            Person ivy  = new Person("ivy");
            Person jan  = new Person("jan");
            
            abe.Prefs  = new List<Person>() {abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay};
            bob.Prefs  = new List<Person>() {cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay};
            col.Prefs  = new List<Person>() {hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan};
            dan.Prefs  = new List<Person>() {ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi};
            ed.Prefs   = new List<Person>() {jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay};
            fred.Prefs = new List<Person>() {bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay};
            gav.Prefs  = new List<Person>() {gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay};
            hal.Prefs  = new List<Person>() {abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee};
            ian.Prefs  = new List<Person>() {hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve};
            jon.Prefs  = new List<Person>() {abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope};
            abi.Prefs  = new List<Person>() {bob, fred, jon, gav, ian, abe, dan, ed, col, hal};
            bea.Prefs  = new List<Person>() {bob, abe, col, fred, gav, dan, ian, ed, jon, hal};
            cath.Prefs = new List<Person>() {fred, bob, ed, gav, hal, col, ian, abe, dan, jon};
            dee.Prefs  = new List<Person>() {fred, jon, col, abe, ian, hal, gav, dan, bob, ed};
            eve.Prefs  = new List<Person>() {jon, hal, fred, dan, abe, gav, col, ed, ian, bob};
            fay.Prefs  = new List<Person>() {bob, abe, ed, ian, jon, dan, fred, gav, col, hal};
            gay.Prefs  = new List<Person>() {jon, gav, hal, fred, bob, abe, col, ed, dan, ian};
            hope.Prefs = new List<Person>() {gav, jon, bob, abe, ian, dan, hal, ed, col, fred};
            ivy.Prefs  = new List<Person>() {ian, col, hal, gav, fred, bob, abe, ed, jon, dan};
            jan.Prefs  = new List<Person>() {ed, hal, gav, abe, bob, jon, col, ian, fred, dan};
            
            List<Person> men = new List<Person>(abi.Prefs);
            
            int freeMenCount = men.Count;
            while (freeMenCount > 0) {
                foreach (Person guy in men) {
                    if (guy.Fiance == null) {
                        Person gal = guy.NextCandidateNotYetProposedTo();
                        if (gal.Fiance == null) {
                            guy.EngageTo(gal);
                            freeMenCount--;
                        } else if (gal.Prefers(guy)) {
                            guy.EngageTo(gal);
                        }
                    }
                }
            }
            
            foreach (Person guy in men) {
                Console.WriteLine("{0} is engaged to {1}", guy.Name, guy.Fiance.Name);
            }
            Console.WriteLine("Stable = {0}", IsStable(men));
            
            Console.WriteLine("\nSwitching fred & jon's partners");
            Person jonsFiance = jon.Fiance;
            Person fredsFiance = fred.Fiance;
            fred.EngageTo(jonsFiance);
            jon.EngageTo(fredsFiance);
            Console.WriteLine("Stable = {0}", IsStable(men));
        }
        
        public static void Main(string[] args)
        {
            DoMarriage();
        }
    }
}
Output:
bob is engaged to cath
fred is engaged to bea
jon is engaged to abi
gav is engaged to gay
ian is engaged to hope
abe is engaged to ivy
dan is engaged to fay
ed is engaged to jan
col is engaged to dee
hal is engaged to eve
Stable = True

Switching fred & jon's partners
Stable = False

C++[edit]

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

const char *men_data[][11] = {
    { "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" }
};
 
const char *women_data[][11] = {
    { "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" }
};

typedef vector<string> PrefList;
typedef map<string, PrefList> PrefMap;
typedef map<string, string> Couples;

// Does 'first' appear before 'second' in preference list?
bool prefers(const PrefList &prefer, const string &first, const string &second)
{
    for (PrefList::const_iterator it = prefer.begin(); it != prefer.end(); ++it)
    {
        if (*it == first) return true;
        if (*it == second) return false;
    }
    return false; // no preference
}

void check_stability(const Couples &engaged, const PrefMap &men_pref, const PrefMap &women_pref)
{
    cout << "Stablility:\n";
    bool stable = true;
    for (Couples::const_iterator it = engaged.begin(); it != engaged.end(); ++it)
    {
        const string &bride = it->first;
        const string &groom = it->second;
        const PrefList &preflist = men_pref.at(groom);

        for (PrefList::const_iterator it = preflist.begin(); it != preflist.end(); ++it)
        {
            if (*it == bride) // he prefers his bride
                break;
            if (prefers(preflist, *it, bride) && // he prefers another woman
                prefers(women_pref.at(*it), groom, engaged.at(*it))) // other woman prefers him
            {
                cout << "\t" << *it <<
                    " prefers " << groom <<
                    " over " << engaged.at(*it) <<
                    " and " << groom <<
                    " prefers " << *it <<
                    " over " << bride << "\n";
                stable = false;
            }
        }
    }
    if (stable) cout << "\t(all marriages stable)\n";
}

int main()
{
    PrefMap men_pref, women_pref;
    queue<string> bachelors;

    // init data structures
    for (int i = 0; i < 10; ++i) // person
    {
        for (int j = 1; j < 11; ++j) // preference
        {
              men_pref[  men_data[i][0]].push_back(  men_data[i][j]);
            women_pref[women_data[i][0]].push_back(women_data[i][j]);
        }
        bachelors.push(men_data[i][0]);
    }

    Couples engaged; // <woman,man>

    cout << "Matchmaking:\n";
    while (!bachelors.empty())
    {
        const string &suitor = bachelors.front();
        const PrefList &preflist = men_pref[suitor];

        for (PrefList::const_iterator it = preflist.begin(); it != preflist.end(); ++it)
        {
            const string &bride = *it;

            if (engaged.find(bride) == engaged.end()) // she's available
            {
                cout << "\t" << bride << " and " << suitor << "\n";
                engaged[bride] = suitor; // hook up
                break;
            }

            const string &groom = engaged[bride];

            if (prefers(women_pref[bride], suitor, groom))
            {
                cout << "\t" << bride << " dumped " << groom << " for " << suitor << "\n";
                bachelors.push(groom); // dump that zero
                engaged[bride] = suitor; // get a hero
                break;
            }
        }
        bachelors.pop(); // pop at the end to not invalidate suitor reference
    }

    cout << "Engagements:\n";
    for (Couples::const_iterator it = engaged.begin(); it != engaged.end(); ++it)
    {
        cout << "\t" << it->first << " and " << it->second << "\n";
    }

    check_stability(engaged, men_pref, women_pref);

    cout << "Perturb:\n";
    std::swap(engaged["abi"], engaged["bea"]);
    cout << "\tengage abi with " << engaged["abi"] << " and bea with " << engaged["bea"] << "\n";

    check_stability(engaged, men_pref, women_pref);
}
Output:
Matchmaking:
	abi and abe
	cath and bob
	hope and col
	ivy and dan
	jan and ed
	bea and fred
	gay and gav
	eve and hal
	hope dumped col for ian
	abi dumped abe for jon
	dee and col
	ivy dumped dan for abe
	fay and dan
Engagements:
	abi and jon
	bea and fred
	cath and bob
	dee and col
	eve and hal
	fay and dan
	gay and gav
	hope and ian
	ivy and abe
	jan and ed
Stablility:
	(all marriages stable)
Perturb:
	engage abi with fred and bea with jon
Stablility:
	bea prefers fred over jon and fred prefers bea over abi
	fay prefers jon over dan and jon prefers fay over bea
	gay prefers jon over gav and jon prefers gay over bea
	eve prefers jon over hal and jon prefers eve over bea

Ceylon[edit]

abstract class Single(name) of Gal | Guy {

    shared String name;
    shared late Single[] preferences;

    shared variable Single? fiance = null;
    shared Boolean free => fiance is Null;

    shared variable Integer currentProposalIndex = 0;

    "Does this single prefer this other single over their fiance?"
    shared Boolean prefers(Single otherSingle) =>
            let (p1 = preferences.firstIndexWhere(otherSingle.equals), f = fiance)
            if (!exists p1)
            then false
            else if (!exists f)
            then true
            else if (exists p2 = preferences.firstIndexWhere(f.equals))
            then p1 < p2
            else false;

    string => name;
}

abstract class Guy(String name) of abe | bob | col | dan | ed | fred | gav | hal | ian | jon extends Single(name) {}

object abe extends Guy("Abe") {}
object bob extends Guy("Bob") {}
object col extends Guy("Col") {}
object dan extends Guy("Dan") {}
object ed extends Guy("Ed") {}
object fred extends Guy("Fred") {}
object gav extends Guy("Gav") {}
object hal extends Guy("Hal") {}
object ian extends Guy("Ian") {}
object jon extends Guy("Jon") {}

abstract class Gal(String name) of abi | bea | cath | dee | eve | fay | gay | hope | ivy | jan extends Single(name) {}

object abi extends Gal("Abi") {}
object bea extends Gal("Bea") {}
object cath extends Gal("Cath") {}
object dee extends Gal("Dee") {}
object eve extends Gal("Eve") {}
object fay extends Gal("Fay") {}
object gay extends Gal("Gay") {}
object hope extends Gal("Hope") {}
object ivy extends Gal("Ivy") {}
object jan extends Gal("Jan") {}

Guy[] guys = `Guy`.caseValues;
Gal[] gals = `Gal`.caseValues;

"The main function. Run this one."
shared void run() {

    abe.preferences = [ abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay ];
    bob.preferences = [ cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay ];
    col.preferences = [ hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan ];
    dan.preferences = [ ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi ];
    ed.preferences = [ jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay ];
    fred.preferences = [ bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay ];
    gav.preferences = [ gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay ];
    hal.preferences = [ abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee ];
    ian.preferences = [ hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve ];
    jon.preferences = [ abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope ];

    abi.preferences = [ bob, fred, jon, gav, ian, abe, dan, ed, col, hal ];
    bea.preferences = [ bob, abe, col, fred, gav, dan, ian, ed, jon, hal ];
    cath.preferences = [ fred, bob, ed, gav, hal, col, ian, abe, dan, jon ];
    dee.preferences = [ fred, jon, col, abe, ian, hal, gav, dan, bob, ed ];
    eve.preferences = [ jon, hal, fred, dan, abe, gav, col, ed, ian, bob ];
    fay.preferences = [ bob, abe, ed, ian, jon, dan, fred, gav, col, hal ];
    gay.preferences = [ jon, gav, hal, fred, bob, abe, col, ed, dan, ian ];
    hope.preferences = [ gav, jon, bob, abe, ian, dan, hal, ed, col, fred ];
    ivy.preferences = [ ian, col, hal, gav, fred, bob, abe, ed, jon, dan ];
    jan.preferences = [ ed, hal, gav, abe, bob, jon, col, ian, fred, dan ];

    print("------ the matchmaking process ------");
    matchmake();
    print("------ the final engagements ------");
    for (guy in guys) {
        print("``guy`` is engaged to ``guy.fiance else "no one"``");
    }
    print("------ is it stable? ------");
    checkStability();
    value temp = jon.fiance;
    jon.fiance = fred.fiance;
    fred.fiance = temp;
    print("------ is it stable after switching jon and fred's partners? ------");
    checkStability();
}

"Match up all the singles with the Gale/Shapley algorithm."
void matchmake() {
    while (true) {
        value singleGuys = guys.filter(Guy.free);
        if (singleGuys.empty) {
            return;
        }
        for (guy in singleGuys) {
            if (exists gal = guy.preferences[guy.currentProposalIndex]) {
                guy.currentProposalIndex++;
                value fiance = gal.fiance;
                if (!exists fiance) {
                    print("``guy`` and ``gal`` just got engaged!");
                    guy.fiance = gal;
                    gal.fiance = guy;
                }
                else {
                    if (gal.prefers(guy)) {
                        print("``gal`` dumped ``fiance`` for ``guy``!");
                        fiance.fiance = null;
                        gal.fiance = guy;
                        guy.fiance = gal;
                    }
                    else {
                        print("``gal`` turned down ``guy`` and stayed with ``fiance``!");
                    }
                }
            }
        }
    }
}

void checkStability() {
    variable value stabilityFlag = true;
    for (gal in gals) {
        for (guy in guys) {
            if (guy.prefers(gal) && gal.prefers(guy)) {
                stabilityFlag = false;
                print("``guy`` prefers ``gal`` over ``guy.fiance else "nobody"`` 
                       and ``gal`` prefers ``guy`` over ``gal.fiance else "nobody"``!".normalized);
            }
        }
    }
    print("``if(!stabilityFlag) then "Not " else ""``Stable!");
}
Output:
------ the matchmaking process ------
Abe and Abi just got engaged!
Bob and Cath just got engaged!
Col and Hope just got engaged!
Dan and Ivy just got engaged!
Ed and Jan just got engaged!
Fred and Bea just got engaged!
Gav and Gay just got engaged!
Abi turned down Hal and stayed with Abe!
Hope dumped Col for Ian!
Abi dumped Abe for Jon!
Abe and Eve just got engaged!
Eve turned down Col and stayed with Abe!
Eve dumped Abe for Hal!
Cath turned down Abe and stayed with Bob!
Abi turned down Col and stayed with Jon!
Ivy dumped Dan for Abe!
Col and Dee just got engaged!
Dan and Fay just got engaged!
------ the final engagements ------
Abe is engaged to Ivy
Bob is engaged to Cath
Col is engaged to Dee
Dan is engaged to Fay
Ed is engaged to Jan
Fred is engaged to Bea
Gav is engaged to Gay
Hal is engaged to Eve
Ian is engaged to Hope
Jon is engaged to Abi
------ is it stable? ------
Stable!
------ is it stable after switching jon and fred's partners? ------
Jon prefers Eve over Bea and Eve prefers Jon over Hal!
Jon prefers Fay over Bea and Fay prefers Jon over Dan!
Jon prefers Gay over Bea and Gay prefers Jon over Gav!
Not Stable!

CoffeeScript[edit]

class Person
  constructor: (@name, @preferences) ->
    @mate = null
    @best_mate_rank = 0
    @rank = {}
    for preference, i in @preferences
      @rank[preference] = i
  
  preferred_mate_name: =>
    @preferences[@best_mate_rank]
    
  reject: =>
    @best_mate_rank += 1
    
  set_mate: (mate) =>
    @mate = mate
  
  offer_mate: (free_mate, reject_mate_cb) =>  
    if @mate
      if @covets(free_mate)
        console.log "#{free_mate.name} steals #{@name} from #{@mate.name}"
        reject_mate_cb @mate
        free_mate.set_mate @
        @set_mate free_mate
      else
        console.log "#{free_mate.name} cannot steal #{@name} from #{@mate.name}"
        reject_mate_cb free_mate
    else
      console.log "#{free_mate.name} gets #{@name} first"
      free_mate.set_mate @
      @set_mate free_mate
      
  happiness: =>
    @rank[@mate.name]
    
  covets: (other_mate) =>
    @rank[other_mate.name] <= @rank[@mate.name]
 
persons_by_name = (persons) ->
  hsh = {}
  for person in persons
    hsh[person.name] = person
  hsh
     
mate_off = (guys, gals) ->
  free_pursuers = (guy for guy in guys)
  guys_by_name = persons_by_name guys
  gals_by_name = persons_by_name gals

  while free_pursuers.length > 0
    free_pursuer = free_pursuers.shift()
    gal_name = free_pursuer.preferred_mate_name()
    gal = gals_by_name[gal_name]
    reject_mate_cb = (guy) ->
      guy.reject()
      free_pursuers.push guy
    gal.offer_mate free_pursuer, reject_mate_cb


report_on_mates = (guys) ->
  console.log "\n----Marriage Report"
  for guy, i in guys
    throw Error("illegal marriage") if guy.mate.mate isnt guy
    console.log guy.name, guy.mate.name, \
      "(his choice #{guy.happiness()}, her choice #{guy.mate.happiness()} )"

report_potential_adulteries = (guys) ->
  for guy1, i in guys
    gal1 = guy1.mate
    for j in [0...i]
      guy2 = guys[j]
      gal2 = guy2.mate
      if guy1.covets(gal2) and gal2.covets(guy1)
        console.log "#{guy1.name} and #{gal2.name} would stray"
      if guy2.covets(gal1) and gal1.covets(guy2)
        console.log "#{guy2.name} and #{gal1.name} would stray"

perturb = (guys) ->
  # mess up marriages by swapping two couples...this is mainly to drive
  # out that report_potential_adulteries will actually work
  guy0 = guys[0]
  guy1 = guys[1]
  gal0 = guy0.mate
  gal1 = guy1.mate
  console.log "\nPerturbing with #{guy0.name}, #{gal0.name}, #{guy1.name}, #{gal1.name}"
  guy0.set_mate gal1
  guy1.set_mate gal0
  gal1.set_mate guy0
  gal0.set_mate guy1


Population = ->
  guy_preferences =
   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']
 
  gal_preferences =
   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']

  guys = (new Person(name, preferences) for name, preferences of guy_preferences)
  gals = (new Person(name, preferences) for name, preferences of gal_preferences)
  [guys, gals]
 
do ->
  [guys, gals] = Population()
  mate_off guys, gals
  report_on_mates guys
  report_potential_adulteries guys
  perturb guys
  report_on_mates guys
  report_potential_adulteries guys
Output:
> coffee stable_marriage.coffee 
abe gets abi first
bob gets cath first
col gets hope first
dan gets ivy first
ed gets jan first
fred gets bea first
gav gets gay first
hal cannot steal abi from abe
ian steals hope from col
jon steals abi from abe
hal gets eve first
col cannot steal eve from hal
abe cannot steal eve from hal
col cannot steal abi from jon
abe cannot steal cath from bob
col gets dee first
abe steals ivy from dan
dan gets fay first

----Marriage Report
abe ivy (his choice 3, her choice 6 )
bob cath (his choice 0, her choice 1 )
col dee (his choice 3, her choice 2 )
dan fay (his choice 1, her choice 5 )
ed jan (his choice 0, her choice 0 )
fred bea (his choice 0, her choice 3 )
gav gay (his choice 0, her choice 1 )
hal eve (his choice 1, her choice 1 )
ian hope (his choice 0, her choice 4 )
jon abi (his choice 0, her choice 2 )

Perturbing with abe, ivy, bob, cath

----Marriage Report
abe cath (his choice 2, her choice 7 )
bob ivy (his choice 8, her choice 5 )
col dee (his choice 3, her choice 2 )
dan fay (his choice 1, her choice 5 )
ed jan (his choice 0, her choice 0 )
fred bea (his choice 0, her choice 3 )
gav gay (his choice 0, her choice 1 )
hal eve (his choice 1, her choice 1 )
ian hope (his choice 0, her choice 4 )
jon abi (his choice 0, her choice 2 )
bob and cath would stray
bob and fay would stray
bob and bea would stray
bob and hope would stray
bob and abi would stray

ColdFusion[edit]

PERSON.CFC

component displayName="Person" accessors="true" {
    property name="Name" type="string";
    property name="MrOrMrsGoodEnough" type="Person";
    property name="UnrealisticExpectations" type="array";
    property name="PersonalHistory" type="array";

    public Person function init( required String name ) {
        setName( arguments.name );
        setPersonalHistory([ getName() & " is on the market." ]);
        this.HotnessScale = 0;
        return this;
    }

    public Boolean function hasSettled() {
        // if we have settled, return true;
        return isInstanceOf( getMrOrMrsGoodEnough(), "Person" );
    }

    public Person function getBestOfWhatIsLeft() {
        // increment the hotness scale...1 is best, 10 is...well...VERY settling.
        this.HotnessScale++;
        // get the match from the current rung in the barrel
        var bestChoice = getUnrealisticExpectations()[ this.HotnessScale ];
        return bestChoice;
    }

    public Boolean function wouldRatherBeWith( required Person person ) {
        // only compare if we've already settled on a potential mate
        if( isInstanceOf( this.getMrOrMrsGoodEnough(), "Person" ) ) {
            // if the new person's hotness is greater (numerically smaller) than our current beau...
            return getHotness( this, arguments.person ) < getHotness( this, this.getMrOrMrsGoodEnough() );
        }
        return false; 
    }

    public Void function settle( required Person person ) {
        if( person.hasSettled() ) {
            // this is the match we want. Force a break up of a previous relationship (sorry!)
            dumpLikeATonOfBricks( person );
        }
        person.setMrOrMrsGoodEnough( this );
        if( hasSettled() ) {
            // this is the match we want, so write a dear john to our current match
            dumpLikeATonOfBricks( this );
        }
        logHookup( arguments.person );
        // we've found the mate of our dreams!
        setMrOrMrsGoodEnough( arguments.person );
    }

    public Void function swing( required Person person ) {
        // get our spouses
        var mySpouse = getMrOrMrsGoodEnough();
        var notMySpouse = arguments.person.getMrOrMrsGoodEnough();
        // swap em'
        setMrOrMrsGoodEnough( notMySpouse );
        person.setMrOrMrsGoodEnough( mySpouse );
    }

    public Void function dumpLikeATonOfBricks( required Person person ) {
        logBreakup( arguments.person );
        person.getMrOrMrsGoodEnough().setMrOrMrsGoodEnough( JavaCast( "null", "" ) );
    }

    public String function psychoAnalyze() {
        logNuptuals();
        logRegrets();
        var personalJourney = "";
        for( var entry in getPersonalHistory() ) {
            personalJourney = personalJourney & entry & "<br />";
        }
        return personalJourney;
    }

    private Numeric function getHotness( required Person pursuer, required Person pursued ) {
        var pursuersExpectations = pursuer.getUnrealisticExpectations();
        var hotnessFactor = 1;
        for( var hotnessFactor=1; hotnessFactor<=arrayLen( pursuersExpectations ); hotnessFactor++ ) {
            if( pursuersExpectations[ hotnessFactor ].getName()==arguments.pursued.getName() ) {
                return hotnessFactor;
            }
        }
    }

    private Void function logRegrets() {
        var spouse = getMrOrMrsGoodEnough();
        var spouseHotness = getHotness( this, spouse );
        var myHotness = getHotness( spouse, this );
        if( spouseHotness == 1 && myHotness == 1 ) {
            arrayAppend( getPersonalHistory(), "Yes, yes, the beautiful people always find happy endings: #getName()# (her ###myHotness#), #spouse.getName()# (his ###spouseHotness#)");
        }
        else if( spouseHotness == myHotness ) {
            arrayAppend( getPersonalHistory(), "#getName()# (her ###myHotness#) was made for #spouse.getName()# (his ###spouseHotness#). How precious.");
        }
        else if( spouseHotness > myHotness ) {
            arrayAppend( getPersonalHistory(), "#getName()# (her ###myHotness#) could have done better than #spouse.getName()# (his ###spouseHotness#). Poor slob.");
        }
        else {
            arrayAppend( getPersonalHistory(), "#getName()# (her ###myHotness#) is a lucky bastard to have landed #spouse.getName()# (his ###spouseHotness#).");
        }
    }

    private Void function logNuptuals() {
        arrayAppend( getPersonalHistory(), "#getName()# has settled for #getMrOrMrsGoodEnough().getName()#." );
    }

    private Void function logHookup( required Person person ) {
        var winnerHotness = getHotness( this, arguments.person );
        var myHotness = getHotness( arguments.person, this );
        arrayAppend( getPersonalHistory(), "#getName()# (her ###myHotness#) is checking out #arguments.person.getName()# (his ###winnerHotness#), but wants to keep his options open.");
    }

    private Void function logBreakup( required Person person ) {
        var scrub = person.getMrOrMrsGoodEnough();
        var scrubHotness = getHotness( person, scrub );
        var myHotness = getHotness( person, this );
        arrayAppend( getPersonalHistory(), "#getName()# is so hot (her ###myHotness#) that #person.getName()# is dumping #scrub.getName()# (her ###scrubHotness#)");
    }
}
INDEX.CFM

<cfscript>
    /**
     * Let's get these crazy kids married!
     * @men.hint The men who want to get married
     */
    function doCreepyMassMarriages( required Array men ) {
        marriagesAreStable = false;
        while( !marriagesAreStable ) {
            marriagesAreStable = true;
            for( man in men ) {
                if( !man.hasSettled() ) {
                    marriagesAreStable = false;
                    sexyLady = man.getBestOfWhatIsLeft();
                    if( !sexyLady.hasSettled() || sexyLady.wouldRatherBeWith( man ) ) {
                        man.settle( sexyLady );
                    }
                }
            }
        }
        return men;
    }

    /**
     * We played God...now let's see if society is going to survive
     * @men.hint The married men
     * @women.hint The married women
     */
    function isSocietyStable( required Array men, required Array women ) {
        // loop over married men
        for( var man in arguments.men ) {
            // loop over married women
            for( var woman in arguments.women ) {
                // if the man does not prefer this woman to his current spouse, and the women
                // doesn't prefer the man to her current spouse, this is the best possible match
                if( man.wouldRatherBeWith( woman ) && woman.wouldRatherBeWith( man ) ) {
                    return false;
                }
            }
        }
        return true;
    }

    // the men
    abe = new Person( "Abe" );
    bob = new Person( "Bob" );
    col = new Person( "Col" );
    dan = new Person( "Dan" );
    ed = new Person( "Ed" );
    fred = new Person( "Fred" );
    gav = new Person( "Gav" );
    hal = new Person( "Hal" );
    ian = new Person( "Ian" );
    jon = new Person( "Jon" );

    men = [ abe, bob, col, dan, ed, fred, gav, hal, ian, jon ];

    // the women
    abi = new Person( "Abi" );
    bea = new Person( "Bea" );
    cath = new Person( "Cath" );
    dee = new Person( "Dee" );
    eve = new Person( "Eve" );
    fay = new Person( "Fay" );
    gay = new Person( "Gay" );
    hope = new Person( "Hope" );
    ivy = new Person( "Ivy" );
    jan = new Person( "Jan" );

    women = [ abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan ];

    // set unrealistic expectations for the men
    abe.setUnrealisticExpectations([ abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay ]);
    bob.setUnrealisticExpectations([ cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay ]);
    col.setUnrealisticExpectations([ hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan ]);
    dan.setUnrealisticExpectations([ ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi ]);
    ed.setUnrealisticExpectations([ jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay ]);
    fred.setUnrealisticExpectations([ bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay ]);
    gav.setUnrealisticExpectations([ gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay ]);
    hal.setUnrealisticExpectations([ abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee ]);
    ian.setUnrealisticExpectations([ hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve ]);
    jon.setUnrealisticExpectations([ abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope ]);
    // set unrealistic expectations for the women
    abi.setUnrealisticExpectations([ bob, fred, jon, gav, ian, abe, dan, ed, col, hal ]);
    bea.setUnrealisticExpectations([ bob, abe, col, fred, gav, dan, ian, ed, jon, hal ]);
    cath.setUnrealisticExpectations([ fred, bob, ed, gav, hal, col, ian, abe, dan, jon ]);
    dee.setUnrealisticExpectations([ fred, jon, col, abe, ian, hal, gav, dan, bob, ed ]);
    eve.setUnrealisticExpectations([ jon, hal, fred, dan, abe, gav, col, ed, ian, bob ]);
    fay.setUnrealisticExpectations([ bob, abe, ed, ian, jon, dan, fred, gav, col, hal ]);
    gay.setUnrealisticExpectations([ jon, gav, hal, fred, bob, abe, col, ed, dan, ian ]);
    hope.setUnrealisticExpectations([ gav, jon, bob, abe, ian, dan, hal, ed, col, fred ]);
    ivy.setUnrealisticExpectations([ ian, col, hal, gav, fred, bob, abe, ed, jon, dan ]);
    jan.setUnrealisticExpectations([ ed, hal, gav, abe, bob, jon, col, ian, fred, dan ]);

    // here comes the bride, duhn, duhn, duh-duhn
    possiblyHappilyMarriedMen = doCreepyMassMarriages( men );
    // let's see who shacked up!
    for( man in possiblyHappilyMarriedMen ) {
        writeoutput( man.psychoAnalyze() & "<br />" );
    }
    // check if society is stable
    if( isSocietyStable( men, women ) ) {
        writeoutput( "Hey, look at that. Creepy social engineering works. Sort of...<br /><br />" );
    }
    // what happens if couples start swingin'?
    jon.swing( fred );
    writeoutput( "Swapping Jon and Fred's wives...will society survive?<br /><br />" );
    // check if society is still stable after the swingers
    if( !isSocietyStable( men, women ) ) {
        writeoutput( "Nope, now everything is broken. Sharing spouses doesn't work, kids.<br />" );
    }
</cfscript>
Output:
Abe is on the market.
Abe (her #6) is checking out Abi (his #1), but wants to keep his options open.
Abe (her #5) is checking out Eve (his #2), but wants to keep his options open.
Abe is so hot (her #7) that Ivy is dumping Dan (her #10)
Abe (her #7) is checking out Ivy (his #4), but wants to keep his options open.
Abe has settled for Ivy.
Abe (her #7) is lucky to have landed Ivy (his #4).

Bob is on the market.
Bob (her #2) is checking out Cath (his #1), but wants to keep his options open.
Bob has settled for Cath.
Bob (her #2) is lucky to have landed Cath (his #1).

Col is on the market.
Col (her #9) is checking out Hope (his #1), but wants to keep his options open.
Col (her #3) is checking out Dee (his #4), but wants to keep his options open.
Col has settled for Dee.
Col (her #3) could have done better than Dee (his #4).

Dan is on the market.
Dan (her #10) is checking out Ivy (his #1), but wants to keep his options open.
Dan (her #6) is checking out Fay (his #2), but wants to keep his options open.
Dan has settled for Fay.
Dan (her #6) is lucky to have landed Fay (his #2).

Ed is on the market.
Ed (her #1) is checking out Jan (his #1), but wants to keep his options open.
Ed has settled for Jan.
Yes, yes, the beautiful people always find happy endings: Ed (her #1), Jan (his #1)

Fred is on the market.
Fred (her #4) is checking out Bea (his #1), but wants to keep his options open.
Fred has settled for Bea.
Fred (her #4) is lucky to have landed Bea (his #1).

Gav is on the market.
Gav (her #2) is checking out Gay (his #1), but wants to keep his options open.
Gav has settled for Gay.
Gav (her #2) is lucky to have landed Gay (his #1).

Hal is on the market.
Hal is so hot (her #2) that Eve is dumping Abe (her #5)
Hal (her #2) is checking out Eve (his #2), but wants to keep his options open.
Hal has settled for Eve.
Hal (her #2) was made for Eve (his #2). How precious.

Ian is on the market.
Ian is so hot (her #5) that Hope is dumping Col (her #9)
Ian (her #5) is checking out Hope (his #1), but wants to keep his options open.
Ian has settled for Hope.
Ian (her #5) is lucky to have landed Hope (his #1).

Jon is on the market.
Jon is so hot (her #3) that Abi is dumping Abe (her #6)
Jon (her #3) is checking out Abi (his #1), but wants to keep his options open.
Jon has settled for Abi.
Jon (her #3) is lucky to have landed Abi (his #1).
// Is society stable?
Hey, look at that. Creepy social engineering works. Sort of...

Swapping Jon and Fred's wives...will society survive?
// How about now? Still stable?
Nope, now everything is broken. Sharing spouses doesn't work, kids.

D[edit]

From the Python and Java versions:

import std.stdio, std.array, std.algorithm, std.string;


string[string] matchmaker(string[][string] guyPrefers,
                          string[][string] girlPrefers) /*@safe*/ {
    string[string] engagedTo;
    string[] freeGuys = guyPrefers.keys;

    while (freeGuys.length) {
        const string thisGuy = freeGuys[0];
        freeGuys.popFront();
        const auto thisGuyPrefers = guyPrefers[thisGuy];
        foreach (girl; thisGuyPrefers) {
            if (girl !in engagedTo) { // girl is free
                engagedTo[girl] = thisGuy;
                break;
            } else {
                string otherGuy = engagedTo[girl];
                string[] thisGirlPrefers = girlPrefers[girl];
                if (thisGirlPrefers.countUntil(thisGuy) <
                    thisGirlPrefers.countUntil(otherGuy)) {
                    // this girl prefers this guy to
                    // the guy she's engagedTo to.
                    engagedTo[girl] = thisGuy;
                    freeGuys ~= otherGuy;
                    break;
                }
                // else no change, keep looking for this guy
            }
        }
    }

    return engagedTo;
}


bool check(bool doPrint=false)(string[string] engagedTo,
                               string[][string] guyPrefers,
                               string[][string] galPrefers) @safe {
    enum MSG = "%s likes %s better than %s and %s " ~
               "likes %s better than their current partner";
    string[string] inverseEngaged;
    foreach (k, v; engagedTo)
        inverseEngaged[v] = k;

    foreach (she, he; engagedTo) {
        auto sheLikes = galPrefers[she];
        auto sheLikesBetter = sheLikes[0 .. sheLikes.countUntil(he)];
        auto heLikes = guyPrefers[he];
        auto heLikesBetter = heLikes[0 .. heLikes.countUntil(she)];
        foreach (guy; sheLikesBetter) {
            auto guysGirl = inverseEngaged[guy];
            auto guyLikes = guyPrefers[guy];

            if (guyLikes.countUntil(guysGirl) >
                guyLikes.countUntil(she)) {
                static if (doPrint)
                    writefln(MSG, she, guy, he, guy, she);
                return false;
            }
        }

        foreach (gal; heLikesBetter) {
            auto girlsGuy = engagedTo[gal];
            auto galLikes = galPrefers[gal];

            if (galLikes.countUntil(girlsGuy) >
                galLikes.countUntil(he)) {
                static if (doPrint)
                    writefln(MSG, he, gal, she, gal, he);
                return false;
            }
        }
    }

    return true;
}


void main() /*@safe*/ {
    auto guyData = "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";

    auto galData = "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";

    string[][string] guyPrefers, galPrefers;
    foreach (line; guyData.splitLines())
        guyPrefers[split(line)[0]] = split(line)[1..$];
    foreach (line; galData.splitLines())
        galPrefers[split(line)[0]] = split(line)[1..$];

    writeln("Engagements:");
    auto engagedTo = matchmaker(guyPrefers, galPrefers);

    writeln("\nCouples:");
    string[] parts;
    foreach (k; engagedTo.keys.sort())
        writefln("%s is engagedTo to %s", k, engagedTo[k]);
    writeln();

    bool c = check!(true)(engagedTo, guyPrefers, galPrefers);
    writeln("Marriages are ", c ? "stable" : "unstable");

    writeln("\n\nSwapping two fiances to introduce an error");
    auto gals = galPrefers.keys.sort();
    swap(engagedTo[gals[0]], engagedTo[gals[1]]);
    foreach (gal; gals[0 .. 2])
        writefln("  %s is now engagedTo to %s", gal, engagedTo[gal]);
    writeln();

    c = check!(true)(engagedTo, guyPrefers, galPrefers);
    writeln("Marriages are ", c ? "stable" : "unstable");
}
Output:
Engagements:

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

Marriages are stable


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

fred likes bea better than abi and bea likes fred better than their current partner
Marriages are unstable

Stronger Version[edit]

import std.stdio, std.algorithm, std.array;

enum F { abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan }
enum M { abe, bob, col, dan, ed, fred, gav, hal, ian, jon }

alias PrefMapF = M[][F];
alias PrefMapM = F[][M];
alias Couples = M[F];

immutable PrefMapF womenPref;
immutable PrefMapM menPref;

static this() pure nothrow @safe {
    with (F) with (M) {
        womenPref = [
             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]
        ];

        menPref = [
             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]
        ];
    }
}

/// Does 'first' appear before 'second' in preference list?
bool prefers(T)(in T[] preference, in T first, in T second)
pure nothrow @safe @nogc if (is(T == F) || is(T == M)) {
    //const found = preference.findAmong([first, second]);
    immutable T[2] two = [first, second];
    const found = preference.findAmong(two[]);
    return !(found.empty || found.front == second);
}

void checkStability(in Couples engaged, in PrefMapM menPref,
                    in PrefMapF womenPref) @safe {
    "Stablility:".writeln;
    bool stable = true;
    foreach (immutable bride, immutable groom; engaged) {
        const prefList = menPref[groom];

        foreach (immutable pr; prefList) {
            if (pr == bride) // He prefers his bride.
                break;

            if (prefers(prefList, pr, bride) &&
                // He prefers another woman.
                prefers(womenPref[pr], groom, engaged[pr])) {
                // Other woman prefers him.
                writeln("\t", pr, " prefers ", groom, " over ",
                        engaged[pr], " and ", groom, " prefers ",
                        pr, " over ", bride);
                stable = false;
            }
        }
    }

    if (stable)
        "\t(all marriages stable)".writeln;
}

void main() /*@safe*/ {
    auto bachelors = menPref.keys.sort().release;// No queue in Phobos.
    Couples engaged;

    "Matchmaking:".writeln;
    while (!bachelors.empty) {
        immutable suitor = bachelors[0];
        bachelors.popFront;
        immutable prefList = menPref[suitor];

        foreach (immutable bride; prefList) {
            if (bride !in engaged) { // She's available.
                writeln("\t", bride, " and ", suitor);
                engaged[bride] = suitor; // Hook up.
                break;
            }

            immutable groom = engaged[bride];
            if (prefers(womenPref[bride], suitor, groom)) {
                writeln("\t", bride, " dumped ", groom,
                        " for ", suitor);
                bachelors ~= groom; // Dump that zero.
                engaged[bride] = suitor; // Get a hero.
                break;
            }
        }
    }

    "Engagements:".writeln;
    foreach (immutable first, immutable second; engaged)
        writeln("\t", first, " and ", second);

    checkStability(engaged, menPref, womenPref);

    "Perturb:".writeln;
    engaged[F.abi].swap(engaged[F.bea]);
    writeln("\tengage abi with ", engaged[F.abi],
            " and bea with ", engaged[F.bea]);

    checkStability(engaged, menPref, womenPref);
}
Output:
Matchmaking:
    abi and abe
    cath and bob
    hope and col
    ivy and dan
    jan and ed
    bea and fred
    gay and gav
    eve and hal
    hope dumped col for ian
    abi dumped abe for jon
    dee and col
    ivy dumped dan for abe
    fay and dan
Engagements:
    abi and jon
    ivy and abe
    eve and hal
    jan and ed
    bea and fred
    fay and dan
    cath and bob
    gay and gav
    hope and ian
    dee and col
Stablility:
    (all marriages stable)
Perturb:
    engage abi with fred and bea with jon
Stablility:
    bea prefers fred over jon and fred prefers bea over abi
    fay prefers jon over dan and jon prefers fay over bea
    gay prefers jon over gav and jon prefers gay over bea
    eve prefers jon over hal and jon prefers eve over bea

EchoLisp[edit]

(lib 'hash)
;; input data
(define M-RANKS 
'(( 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)))

(define W-RANKS 
'((  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)))

;; build preferences hash
(define (set-prefs ranks  prefs)
    (for/list ((r ranks))
        (hash-set prefs (first r) (rest r))
        (first r)))
        
(define (engage  m w)    (hash-set ENGAGED m w) (hash-set ENGAGED w m) (writeln  m w '👫 ))
(define (disengage  m w) (hash-remove! ENGAGED m ) (hash-remove! ENGAGED w) (writeln '💔 m w))
(define (engaged x)      (hash-ref ENGAGED x))
(define (free? x)        (not (engaged x)))
(define (free-man men)   (for ((man men)) #:break (free? man) => man  #f))


(define (prefers? prefs x a b) (member b  (member a (hash-ref prefs x))))
;; get first choice and remove it from prefs list
(define (first-choice prefs m) 
    (define w (first (hash-ref prefs m)))
    (hash-set prefs m (rest (hash-ref prefs m)))
    w)
    
;; sets ENGAGED couples
;;  https//en.wikipedia.org/wiki/Stable_marriage_problem

(define (stableMatching  (prefs (make-hash)) (m) (w))
(define-global 'ENGAGED (make-hash))
  (define men   (set-prefs  M-RANKS prefs))
  (define women (set-prefs  W-RANKS prefs))
    (while (setv! m (free-man men))
        (set! w (first-choice prefs m))
        (if (free? w)
            (engage m w)
            (let [(dumped (engaged w))]
            (when (prefers? prefs w m dumped)
                (disengage w dumped)
                (engage w m)))))
 (hash->list ENGAGED))
                
;; input : ENGAGED couples
(define (checkStable (prefs (make-hash)))
  (define men   (set-prefs  M-RANKS  prefs))
  (define women (set-prefs  W-RANKS  prefs))
	(for* [(man men) (woman women)]
	#:continue (equal? woman (engaged man))
			(when (and 
					(prefers? prefs man woman (engaged man))
					(prefers? prefs woman man (engaged woman)))
					(error 'not-stable (list man woman)))))
Output:
(stableMatching)
👫     abe     abi    
👫     bob     cath    
👫     col     hope    
👫     dan     ivy    
👫     ed     jan    
👫     fred     bea    
👫     gav     gay    
👫     hal     eve    
💔     hope     col    
👫     hope     ian    
👫     col     dee    
💔     abi     abe    
👫     abi     jon    
💔     ivy     dan    
👫     ivy     abe    
👫     dan     fay    
  ((abe . ivy) (abi . jon) (bob . cath) (cath . bob) (col . dee) (hope . ian) (dan . fay) (ivy . abe) (ed . jan)
 (jan . ed) (fred . bea) (bea . fred) (gav . gay) (gay . gav) (hal . eve) (eve . hal) (ian . hope) (dee . col) (jon . abi) (fay . dan))

(disengage 'abe 'ivy)
(disengage 'hope 'ian)
(engage 'abe 'hope)
(engage 'ivy 'ian)
(checkStable)

💔     abe     ivy    
💔     hope     ian    
abe     hope     👫    
ivy     ian     👫    
😡 error: not-stable (abe bea)

F#[edit]

let menPrefs =
  Map.ofList
            ["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"];
            ]

let womenPrefs =
   Map.ofList
              ["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"];
              ]

let men = menPrefs |> Map.toList |> List.map fst |> List.sort
let women = womenPrefs |> Map.toList |> List.map fst |> List.sort


type Configuration =
 {
   proposed: Map<string,string list>; // man -> list of women
   wifeOf: Map<string, string>; // man -> woman
   husbandOf: Map<string, string>;  // woman -> man
 }


// query functions

let isFreeMan config man = config.wifeOf.TryFind man = None

let isFreeWoman config woman = config.husbandOf.TryFind woman = None

let hasProposedTo config man woman =
  defaultArg (config.proposed.TryFind(man)) []
  |> List.exists ((=) woman)

// helper
let negate f = fun x -> not (f x)

// returns those 'women' who 'man' has not proposed to before
let notProposedBy config man women = List.filter (negate (hasProposedTo config man)) women
 
let prefers (prefs:Map<string,string list>) w m1 m2 =
  let order = prefs.[w]
  let m1i = List.findIndex ((=) m1) order
  let m2i = List.findIndex ((=) m2) order
  m1i < m2i

let womanPrefers = prefers womenPrefs
let manPrefers = prefers menPrefs

// returns the women that m likes better than his current fiancée
let preferredWomen config m =
  let w = config.wifeOf.[m]
  women
  |> List.filter (fun w' -> manPrefers m w' w)  // '

// whether there is a woman who m likes better than his current fiancée
// and who also likes him better than her current fiancé
let prefersAWomanWhoAlsoPrefersHim config m =
  preferredWomen config m
  |> List.exists (fun w -> womanPrefers w m config.husbandOf.[w])

let isStable config =
  not (List.exists (prefersAWomanWhoAlsoPrefersHim config) men)


// modifiers (return new configurations)

let engage config man woman =
  { config with wifeOf = config.wifeOf.Add(man, woman);
                husbandOf = config.husbandOf.Add(woman, man) }

let breakOff config man =
  let woman = config.wifeOf.[man]
  { config with wifeOf = config.wifeOf.Remove(man);
                husbandOf = config.husbandOf.Remove(woman) }

let propose config m w =
  // remember the proposition
  let proposedByM = defaultArg (config.proposed.TryFind m) []
  let proposed' = config.proposed.Add(m, w::proposedByM) // '
  let config = { config with proposed = proposed'}  // '
  // actually try to engage
  if isFreeWoman config w then engage config m w
  else
    let m' = config.husbandOf.[w] // '
    if womanPrefers w m m' then // '
      let config = breakOff config m' // '
      engage config m w
    else
      config

// do one step of the algorithm; returns None if no more steps are possible
let step config : Configuration option =
  let freeMen = men |> List.filter (isFreeMan config)
  let menWhoCanPropose =
    freeMen |>
    List.filter (fun man -> (notProposedBy config man women) <> [] )
  match menWhoCanPropose with
  | [] -> None
  | m::_ -> let unproposedByM = menPrefs.[m] |> notProposedBy config m
            // w is automatically the highest ranked because menPrefs.[m] is the source
            let w = List.head unproposedByM
            Some( propose config m w )
              
let rec loop config =
  match step config with
  | None -> config
  | Some config' -> loop config' // '


// find solution and print it
let solution = loop { proposed = Map.empty<string, string list>;
                      wifeOf = Map.empty<string, string>;
                      husbandOf = Map.empty<string, string> }

for woman, man in Map.toList solution.husbandOf do
  printfn "%s is engaged to %s" woman man

printfn "Solution is stable: %A" (isStable solution)


// create unstable configuration by perturbing the solution
let perturbed = 
  let gal0 = women.[0]
  let gal1 = women.[1]
  let guy0 = solution.husbandOf.[gal0]
  let guy1 = solution.husbandOf.[gal1]
  { solution with wifeOf = solution.wifeOf.Add( guy0, gal1 ).Add( guy1, gal0 );
                  husbandOf = solution.husbandOf.Add( gal0, guy1 ).Add( gal1, guy0 ) }

printfn "Perturbed is stable: %A" (isStable perturbed)
Output:
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
Solution is stable: true
Perturbed is stable: false

Go[edit]

package main

import "fmt"

// Asymetry in the algorithm suggests different data structures for the
// map value types of the proposers and the recipients.  Proposers go down
// their list of preferences in order, and do not need random access.
// Recipients on the other hand must compare their preferences to arbitrary
// proposers.  A slice is adequate for proposers, but a map allows direct
// lookups for recipients and avoids looping code.
type proposers map[string][]string
    
var mPref = proposers{
    "abe": []string{
        "abi", "eve", "cath", "ivy", "jan",
        "dee", "fay", "bea", "hope", "gay"},
    "bob": []string{
        "cath", "hope", "abi", "dee", "eve",
        "fay", "bea", "jan", "ivy", "gay"},
    "col": []string{
        "hope", "eve", "abi", "dee", "bea",
        "fay", "ivy", "gay", "cath", "jan"},
    "dan": []string{
        "ivy", "fay", "dee", "gay", "hope",
        "eve", "jan", "bea", "cath", "abi"},
    "ed": []string{
        "jan", "dee", "bea", "cath", "fay",
        "eve", "abi", "ivy", "hope", "gay"},
    "fred": []string{
        "bea", "abi", "dee", "gay", "eve",
        "ivy", "cath", "jan", "hope", "fay"},
    "gav": []string{
        "gay", "eve", "ivy", "bea", "cath",
        "abi", "dee", "hope", "jan", "fay"},
    "hal": []string{
        "abi", "eve", "hope", "fay", "ivy",
        "cath", "jan", "bea", "gay", "dee"},
    "ian": []string{
        "hope", "cath", "dee", "gay", "bea",
        "abi", "fay", "ivy", "jan", "eve"},
    "jon": []string{
        "abi", "fay", "jan", "gay", "eve",
        "bea", "dee", "cath", "ivy", "hope"},
}

type recipients map[string]map[string]int

var wPref = recipients{
    "abi": map[string]int{
        "bob": 1, "fred": 2, "jon": 3, "gav": 4, "ian": 5,
        "abe": 6, "dan": 7, "ed": 8, "col": 9, "hal": 10},
    "bea": map[string]int{
        "bob": 1, "abe": 2, "col": 3, "fred": 4, "gav": 5,
        "dan": 6, "ian": 7, "ed": 8, "jon": 9, "hal": 10},
    "cath": map[string]int{
        "fred": 1, "bob": 2, "ed": 3, "gav": 4, "hal": 5,
        "col": 6, "ian": 7, "abe": 8, "dan": 9, "jon": 10},
    "dee": map[string]int{
        "fred": 1, "jon": 2, "col": 3, "abe": 4, "ian": 5,
        "hal": 6, "gav": 7, "dan": 8, "bob": 9, "ed": 10},
    "eve": map[string]int{
        "jon": 1, "hal": 2, "fred": 3, "dan": 4, "abe": 5,
        "gav": 6, "col": 7, "ed": 8, "ian": 9, "bob": 10},
    "fay": map[string]int{
        "bob": 1, "abe": 2, "ed": 3, "ian": 4, "jon": 5,
        "dan": 6, "fred": 7, "gav": 8, "col": 9, "hal": 10},
    "gay": map[string]int{
        "jon": 1, "gav": 2, "hal": 3, "fred": 4, "bob": 5,
        "abe": 6, "col": 7, "ed": 8, "dan": 9, "ian": 10},
    "hope": map[string]int{
        "gav": 1, "jon": 2, "bob": 3, "abe": 4, "ian": 5,
        "dan": 6, "hal": 7, "ed": 8, "col": 9, "fred": 10},
    "ivy": map[string]int{
        "ian": 1, "col": 2, "hal": 3, "gav": 4, "fred": 5,
        "bob": 6, "abe": 7, "ed": 8, "jon": 9, "dan": 10},
    "jan": map[string]int{
        "ed": 1, "hal": 2, "gav": 3, "abe": 4, "bob": 5,
        "jon": 6, "col": 7, "ian": 8, "fred": 9, "dan": 10},
}

func main() {
    // get parings by Gale/Shapley algorithm
    ps := pair(mPref, wPref)
    // show results
    fmt.Println("\nresult:")
    if !validateStable(ps, mPref, wPref) {
        return 
    }
    // perturb
    for {
        i := 0 
        var w2, m2 [2]string
        for w, m := range ps {
            w2[i] = w
            m2[i] = m
            if i == 1 {
                break
            }
            i++
        }
        fmt.Println("\nexchanging partners of", m2[0], "and", m2[1])
        ps[w2[0]] = m2[1]
        ps[w2[1]] = m2[0] 
        // validate perturbed parings
        if !validateStable(ps, mPref, wPref) {
            return
        }
        // if those happened to be stable as well, perturb more
    }
}   

type parings map[string]string // map[recipient]proposer (or map[w]m)
    
// Pair implements the Gale/Shapley algorithm.
func pair(pPref proposers, rPref recipients) parings {
    // code is destructive on the maps, so work with copies
    pFree := proposers{}
    for k, v := range pPref {
        pFree[k] = append([]string{}, v...)
    }
    rFree := recipients{}
    for k, v := range rPref {
        rFree[k] = v
    }
    // struct only used in this function.
    // preferences must be saved in case engagement is broken.
    type save struct {
        proposer string
        pPref    []string
        rPref    map[string]int
    }
    proposals := map[string]save{} // key is recipient (w)

    // WP pseudocode comments prefaced with WP: m is proposer, w is recipient.
    // WP: while ∃ free man m who still has a woman w to propose to
    for len(pFree) > 0 { // while there is a free proposer,
        var proposer string
        var ppref []string
        for proposer, ppref = range pFree {
            break // pick a proposer at random, whatever range delivers first.
        }
        if len(ppref) == 0 {
            continue // if proposer has no possible recipients, skip
        }
        // WP: w = m's highest ranked such woman to whom he has not yet proposed
        recipient := ppref[0] // highest ranged is first in list.
        ppref = ppref[1:]     // pop from list
        var rpref map[string]int
        var ok bool
        // WP: if w is free
        if rpref, ok = rFree[recipient]; ok {
            // WP: (m, w) become engaged
            // (common code follows if statement)
        } else {
            // WP: else some pair (m', w) already exists
            s := proposals[recipient] // get proposal saved preferences
            // WP: if w prefers m to m'
            if s.rPref[proposer] < s.rPref[s.proposer] {
                fmt.Println("engagement broken:", recipient, s.proposer)
                // WP: m' becomes free
                pFree[s.proposer] = s.pPref // return proposer to the map
                // WP: (m, w) become engaged
                rpref = s.rPref
                // (common code follows if statement)
            } else {
                // WP: else (m', w) remain engaged
                pFree[proposer] = ppref // update preferences in map
                continue
            } 
        }
        fmt.Println("engagement:", recipient, proposer)
        proposals[recipient] = save{proposer, ppref, rpref}
        delete(pFree, proposer)
        delete(rFree, recipient)
    }
    // construct return value 
    ps := parings{}
    for recipient, s := range proposals {
        ps[recipient] = s.proposer
    }
    return ps
}

func validateStable(ps parings, pPref proposers, rPref recipients) bool {
    for r, p := range ps {
        fmt.Println(r, p)
    }
    for r, p := range ps {
        for _, rp := range pPref[p] {
            if rp == r {
                break
            }
            rprefs := rPref[rp]
            if rprefs[p] < rprefs[ps[rp]] {
                fmt.Println("unstable.")
                fmt.Printf("%s and %s would prefer each other over"+
                    " their current pairings.\n", p, rp)
                return false
            }
        }
    }
    fmt.Println("stable.")
    return true
}
Output:
engagement: hope col
engagement: bea fred
engagement: ivy dan
engagement: cath bob
engagement: abi abe
engagement broken: abi abe
engagement: abi jon
engagement: gay gav
engagement: eve abe
engagement: jan ed
engagement broken: hope col
engagement: hope ian
engagement: dee col
engagement broken: eve abe
engagement: eve hal
engagement broken: ivy dan
engagement: ivy abe
engagement: fay dan

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

exchanging partners of fred and dan
ivy abe
bea dan
fay fred
dee col
cath bob
hope ian
eve hal
jan ed
abi jon
gay gav
unstable.
dan and fay would prefer each other over their current pairings.

Groovy[edit]

Translation of: Java
(more or less) Uses explicit maps for preference ranking rather than list position. Uses Man and Woman enumerated types instead of string names, in order to take advantage of compile time type and constant checking to help keep the playas straight without a scorecard.

"Stable Matching" Solution:

import static Man.*
import static Woman.*

Map<Woman,Man> match(Map<Man,Map<Woman,Integer>> guysGalRanking, Map<Woman,Map<Man,Integer>> galsGuyRanking) {
    Map<Woman,Man> engagedTo = new TreeMap()
    List<Man> freeGuys = (Man.values()).clone()
    while(freeGuys) {
        Man thisGuy = freeGuys[0]
        freeGuys -= thisGuy
        List<Woman> guyChoices = Woman.values().sort{ she -> - guysGalRanking[thisGuy][she] }
        for(Woman girl in guyChoices) {
            if(! engagedTo[girl]) {
                engagedTo[girl] = thisGuy
                break
            } else {
                Man thatGuy = engagedTo[girl]
                if (galsGuyRanking[girl][thisGuy] > galsGuyRanking[girl][thatGuy]) {
                    engagedTo[girl] = thisGuy
                    freeGuys << thatGuy
                    break
                }
            }
        }
    }
    engagedTo
}

"Stability Checking" Solution: (Could do more to eliminate common code. Maybe later.)

boolean isStable(Map<Woman,Man> matches, Map<Man,Map<Woman,Integer>> guysGalRanking, Map<Woman,Map<Man,Integer>> galsGuyRanking) {
    matches.collect{ girl, guy ->
        int guysRank = galsGuyRanking[girl][guy]
        List<Man> sheLikesBetter = Man.values().findAll{ he -> galsGuyRanking[girl][he] > guysRank }
        for(Man otherGuy : sheLikesBetter) {
            Woman otherGuyFiancee = matches.find{ pair -> pair.value == otherGuy }.key
            if(guysGalRanking[otherGuy][girl] > guysGalRanking[otherGuy][otherGuyFiancee]) {
                println """O. M. G. ... ${otherGuy} likes ${girl} better than ${otherGuyFiancee}, and ${girl} likes ${otherGuy} better than ${guy}!
                            I am TOTALLY 'shipping ${girl} and ${otherGuy} now!"""
                return false
            } 
        }
        
        int galsRank = guysGalRanking[guy][girl]
        List<Woman> heLikesBetter = Woman.values().findAll{ she -> guysGalRanking[guy][she] > galsRank }
        for(Woman otherGal : heLikesBetter) {
            Man otherGalFiance = matches[otherGal]
            if(galsGuyRanking[otherGal][guy] > galsGuyRanking[otherGal][otherGalFiance]) {
                println """O. M. G. ... ${otherGal} likes ${guy} better than ${otherGalFiance}, and ${guy} likes ${otherGal} better than ${girl}!
                            I am TOTALLY 'shipping ${guy} and ${otherGal} now!"""
                return false
            } 
        }
        true
    }.every()
}

Test (Stable and Perturbed):

enum Man {
    abe, bob, col, dan, ed, fred, gav, hal, ian, jon
}

enum Woman {
    abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan
}

Map<Man,Map<Woman,Integer>> mansWomanRanking = [
    (abe): [(abi):10, (eve):9, (cath):8, (ivy):7, (jan):6, (dee):5, (fay):4, (bea):3, (hope):2, (gay):1],
    (bob): [(cath):10, (hope):9, (abi):8, (dee):7, (eve):6, (fay):5, (bea):4, (jan):3, (ivy):2, (gay):1],
    (col): [(hope):10, (eve):9, (abi):8, (dee):7, (bea):6, (fay):5, (ivy):4, (gay):3, (cath):2, (jan):1],
    (dan): [(ivy):10, (fay):9, (dee):8, (gay):7, (hope):6, (eve):5, (jan):4, (bea):3, (cath):2, (abi):1],
    (ed):  [(jan):10, (dee):9, (bea):8, (cath):7, (fay):6, (eve):5, (abi):4, (ivy):3, (hope):2, (gay):1],
    (fred):[(bea):10, (abi):9, (dee):8, (gay):7, (eve):6, (ivy):5, (cath):4, (jan):3, (hope):2, (fay):1],
    (gav): [(gay):10, (eve):9, (ivy):8, (bea):7, (cath):6, (abi):5, (dee):4, (hope):3, (jan):2, (fay):1],
    (hal): [(abi):10, (eve):9, (hope):8, (fay):7, (ivy):6, (cath):5, (jan):4, (bea):3, (gay):2, (dee):1],
    (ian): [(hope):10, (cath):9, (dee):8, (gay):7, (bea):6, (abi):5, (fay):4, (ivy):3, (jan):2, (eve):1],
    (jon): [(abi):10, (fay):9, (jan):8, (gay):7, (eve):6, (bea):5, (dee):4, (cath):3, (ivy):2, (hope):1],
]
 
Map<Woman,List<Man>> womansManRanking = [
    (abi): [(bob):10, (fred):9, (jon):8, (gav):7, (ian):6, (abe):5, (dan):4, (ed):3, (col):2, (hal):1],
    (bea): [(bob):10, (abe):9, (col):8, (fred):7, (gav):6, (dan):5, (ian):4, (ed):3, (jon):2, (hal):1],
    (cath):[(fred):10, (bob):9, (ed):8, (gav):7, (hal):6, (col):5, (ian):4, (abe):3, (dan):2, (jon):1],
    (dee): [(fred):10, (jon):9, (col):8, (abe):7, (ian):6, (hal):5, (gav):4, (dan):3, (bob):2, (ed):1],
    (eve): [(jon):10, (hal):9, (fred):8, (dan):7, (abe):6, (gav):5, (col):4, (ed):3, (ian):2, (bob):1],
    (fay): [(bob):10, (abe):9, (ed):8, (ian):7, (jon):6, (dan):5, (fred):4, (gav):3, (col):2, (hal):1],
    (gay): [(jon):10, (gav):9, (hal):8, (fred):7, (bob):6, (abe):5, (col):4, (ed):3, (dan):2, (ian):1],
    (hope):[(gav):10, (jon):9, (bob):8, (abe):7, (ian):6, (dan):5, (hal):4, (ed):3, (col):2, (fred):1],
    (ivy): [(ian):10, (col):9, (hal):8, (gav):7, (fred):6, (bob):5, (abe):4, (ed):3, (jon):2, (dan):1],
    (jan): [(ed):10, (hal):9, (gav):8, (abe):7, (bob):6, (jon):5, (col):4, (ian):3, (fred):2, (dan):1],
]

// STABLE test
Map<Woman,Man> matches = match(mansWomanRanking, womansManRanking)
matches.each { w, m ->
    println "${w} (his '${mansWomanRanking[m][w]}' girl) is engaged to ${m} (her '${womansManRanking[w][m]}' guy)"
}
assert matches.keySet() == Woman.values() as Set
assert matches.values() as Set == Man.values() as Set
println ''

assert isStable(matches, mansWomanRanking, womansManRanking)

// PERTURBED test
println 'Swapping partners now ...'
def temp = matches[abi]
matches[abi] = matches[bea]
matches[bea] = temp
matches.each { w, m ->
    println "${w} (his '${mansWomanRanking[m][w]}' girl) is engaged to ${m} (her '${womansManRanking[w][m]}' guy)"
}
println ''

assert ! isStable(matches, mansWomanRanking, womansManRanking)
Output:
abi (his '10' girl) is engaged to jon (her '8' guy)
bea (his '10' girl) is engaged to fred (her '7' guy)
cath (his '10' girl) is engaged to bob (her '9' guy)
dee (his '7' girl) is engaged to col (her '8' guy)
eve (his '9' girl) is engaged to hal (her '9' guy)
fay (his '9' girl) is engaged to dan (her '5' guy)
gay (his '10' girl) is engaged to gav (her '9' guy)
hope (his '10' girl) is engaged to ian (her '6' guy)
ivy (his '7' girl) is engaged to abe (her '4' guy)
jan (his '10' girl) is engaged to ed (her '10' guy)

Swapping partners now ...
abi (his '9' girl) is engaged to fred (her '9' guy)
bea (his '5' girl) is engaged to jon (her '2' guy)
cath (his '10' girl) is engaged to bob (her '9' guy)
dee (his '7' girl) is engaged to col (her '8' guy)
eve (his '9' girl) is engaged to hal (her '9' guy)
fay (his '9' girl) is engaged to dan (her '5' guy)
gay (his '10' girl) is engaged to gav (her '9' guy)
hope (his '10' girl) is engaged to ian (her '6' guy)
ivy (his '7' girl) is engaged to abe (her '4' guy)
jan (his '10' girl) is engaged to ed (her '10' guy)

O. M. G. ... bea likes fred better than jon, and fred likes bea better than abi!
                            I am TOTALLY 'shipping fred and bea now!
O. M. G. ... fred likes bea better than abi, and bea likes fred better than jon!
                            I am TOTALLY 'shipping bea and fred now!
O. M. G. ... jon likes eve better than bea, and eve likes jon better than hal!
                            I am TOTALLY 'shipping eve and jon now!
O. M. G. ... jon likes fay better than bea, and fay likes jon better than dan!
                            I am TOTALLY 'shipping fay and jon now!
O. M. G. ... jon likes gay better than bea, and gay likes jon better than gav!
                            I am TOTALLY 'shipping gay and jon now!

Haskell[edit]

The solution[edit]

The Gale/Shapley algorithm is formulated via iterative changing of the state. In Haskell it is possible to implement this approach by pure function iterations.

The state here consists of the list of free guys and associative preferences lists for guys and girls correspondingly. In order to simplify the access to elements of the state we use lenses.

{-# LANGUAGE TemplateHaskell #-}
import Lens.Micro
import Lens.Micro.TH
import Data.List (union, delete)

type Preferences a = (a, [a])
type Couple a = (a,a)
data State a = State { _freeGuys :: [a]
                     , _guys :: [Preferences a]
                     , _girls :: [Preferences a]}

makeLenses ''State

Lenses allow us to get access to each person in the state, and even to the associated preference list:

name n = lens get set
  where get = head . dropWhile ((/= n).fst)
        set assoc (_,v) = let (prev, _:post) = break ((== n).fst) assoc
                      in prev ++ (n, v):post

fianceesOf n = guys.name n._2
fiancesOf n = girls.name n._2

Note that in following we use lens operators:

 ^.  -- access to a field
 %~  -- modification of a field
 .~  -- setting a field the value

Further we use a trick: guys list girls in a descending order of preference (the most liked is the first), while girls expect guys in opposite order -- the most liked is the last. In any case, we assume that the current best choice for guys and for girls is expected to appear on the top of their preference lists.

With these tools and notes we are ready to implement the Gale/Shapley algorithm and the stability test as they are given in a textbook:

stableMatching :: Eq a => State a -> [Couple a]
stableMatching = getPairs . until (null._freeGuys) step
  where
    getPairs s = map (_2 %~ head) $ s^.guys 

step :: Eq a => State a -> State a
step s = foldl propose s (s^.freeGuys)
  where
    propose s guy =
      let girl                = s^.fianceesOf guy & head
          bestGuy : otherGuys = s^.fiancesOf girl
          modify
            | guy == bestGuy       = freeGuys %~ delete guy
            | guy `elem` otherGuys = (fiancesOf girl %~ dropWhile (/= guy)) .
                                     (freeGuys %~ guy `replaceBy` bestGuy)
            | otherwise            = fianceesOf guy %~ tail
      in modify s

    replaceBy x y [] = []
    replaceBy x y (h:t) | h == x = y:t
                        | otherwise = h:replaceBy x y t

unstablePairs :: Eq a => State a -> [Couple a] -> [(Couple a, Couple a)]
unstablePairs s pairs =
  [ ((m1, w1), (m2,w2)) | (m1, w1) <- pairs
                        , (m2,w2) <- pairs
                        , m1 /= m2
                        , let fm = s^.fianceesOf m1
                        , elemIndex w2 fm < elemIndex w1 fm
                        , let fw = s^.fiancesOf w2
                        , elemIndex m2 fw < elemIndex m1 fw ]

This solution works not only for strings, but for any equable data.

The task[edit]

Here are the given preferences:

guys0 =
  [("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"])]
  
girls0 = 
  [("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"])]

The initial state:

s0 = State (fst <$> guys0) guys0 ((_2 %~ reverse) <$> girls0)

And the solution:

λ> let pairs = stableMatching s0
λ> mapM_ print pairs
("abe","ivy")
("bob","cath")
("col","dee")
("dan","fay")
("ed","jan")
("fred","bea")
("gav","gay")
("hal","eve")
("ian","hope")
("jon","abi")
λ> unstablePairs s0 pairs
[]

Lets' make some perturbations: swap fiancees of abe and bob:

λ> let fiance n = name n._2
λ> let pairs' = pairs & (fiance "abe" .~ "cath") & (fiance "bob" .~ "ivy")
λ> mapM_ print $ unstablePairs s0 pairs'
(("bob","ivy"),("abe","cath"))
(("bob","ivy"),("dan","fay"))
(("bob","ivy"),("fred","bea"))
(("bob","ivy"),("ian","hope"))
(("bob","ivy"),("jon","abi"))

Icon and Unicon[edit]

link printf

procedure main()
   smd := IsStable(ShowEngaged(StableMatching(setup())))   
   IsStable(ShowEngaged(Swap(\smd,smd.women[1],smd.women[2]))) 
end

procedure index(L,x)                         #: return index of value or fail
   return ( L[i := 1 to *L] === x, i)
end

procedure ShowEngaged(smd)                   #: Show who's hooked up
   printf("\nEngagements:\n")
   every w := !smd.women do
      printf("%s is engaged to %s\n",w,smd.engaged[w])
   return smd
end

procedure Swap(smd,x0,x1)                    #: swap two couples by m or w   
   printf("\nSwapping %s and %s\n",x0,x1)
   e := smd.engaged
   e[x0] :=: e[x1]                           # swap partners
   e[e[x0]] := e[e[x1]]
   return smd
end   

procedure IsStable(smd)                      #: validate stability
   stable := 1                                               # assumption
   printf("\n")
   every mp := smd.prefs[m := !smd.men] &                    # man & pref
         w := mp[index(mp,smd.engaged[m])-1 to 1 by -1] do { # better choices 
      wp := smd.prefs[w]                                     # her choices
      if index(wp,smd.engaged[w]) > index(wp,m) then {
         printf("Engagement of %s to %s is unstable.\n",w,m)
         stable := &null                                     # broken
         }
      }
   if \stable then {
      printf("Engagments are all stable.\n")
      return smd
      }
end

procedure StableMatching(smd)                #: match making 
   freemen   := copy(smd.men)                # Initialize all m memberof M 
   freewomen := set(smd.women)               # ... and w memberof W to free
   every (prefmen := table())[m := !freemen] := copy(smd.prefs[m])
   smd.engaged := engaged := table()
   printf("\nMatching:\n")   
   while m := get(freemen) do {                 # next freeman
      while w := get(prefmen[m]) do  {          # . with prpoposals left
         if member(freewomen,w) then {          # . . is she free?
            engaged[m] := w                     # . . . (m, w) 
            engaged[w] := m
            delete(freewomen,w)
            printf("%s accepted %s's proposal\n",w,m)
            break
            }
         else {                                 # . . no, she's engaged         
            m0 := engaged[w]                    #     to m0                  
            if index(smd.prefs[w],m) < index(smd.prefs[w],m0) then {  
               engaged[m] := w                  # (m, w) become engaged
               engaged[w] := m
               delete(freewomen,w)
               engaged[m0] := &null             # m' becomes free
               put(freemen,m0)   
               printf("%s chose %s over %s\n",w,m,m0)
               break
               }
            else next                          # she's happier as is 
         }
      }
   }
   return smd
end

record sm_data(men,women,prefs,engaged)  #: everyones data

procedure setup()                        #: setup everyones data
   X := sm_data()
   X.men   := ["abe","bob","col","dan","ed","fred","gav","hal","ian","jon"]
   X.women := ["abi","bea","cath","dee","eve","fay","gay","hope","ivy","jan"]
   
   if *X.men ~= *(M := set(X.men)) then runerr(500,X.men)       # duplicate? 
   if *X.women ~= *(W := set(X.women)) then runerr(500,X.women) # duplicate?
   if *(B := M**W) ~= 0 then runerr(500,B)                      # intersect?
   
   X.prefs := p := table()
   
   p["abe"]  := ["abi","eve","cath","ivy","jan","dee","fay","bea","hope","gay"]
   p["bob"]  := ["cath","hope","abi","dee","eve","fay","bea","jan","ivy","gay"]
   p["col"]  := ["hope","eve","abi","dee","bea","fay","ivy","gay","cath","jan"]
   p["dan"]  := ["ivy","fay","dee","gay","hope","eve","jan","bea","cath","abi"]
   p["ed"]   := ["jan","dee","bea","cath","fay","eve","abi","ivy","hope","gay"]
   p["fred"] := ["bea","abi","dee","gay","eve","ivy","cath","jan","hope","fay"]
   p["gav"]  := ["gay","eve","ivy","bea","cath","abi","dee","hope","jan","fay"]
   p["hal"]  := ["abi","eve","hope","fay","ivy","cath","jan","bea","gay","dee"]
   p["ian"]  := ["hope","cath","dee","gay","bea","abi","fay","ivy","jan","eve"]
   p["jon"]  := ["abi","fay","jan","gay","eve","bea","dee","cath","ivy","hope"]
   
   p["abi"]  := ["bob","fred","jon","gav","ian","abe","dan","ed","col","hal"]
   p["bea"]  := ["bob","abe","col","fred","gav","dan","ian","ed","jon","hal"]
   p["cath"] := ["fred","bob","ed","gav","hal","col","ian","abe","dan","jon"]
   p["dee"]  := ["fred","jon","col","abe","ian","hal","gav","dan","bob","ed"]
   p["eve"]  := ["jon","hal","fred","dan","abe","gav","col","ed","ian","bob"]
   p["fay"]  := ["bob","abe","ed","ian","jon","dan","fred","gav","col","hal"]
   p["gay"]  := ["jon","gav","hal","fred","bob","abe","col","ed","dan","ian"]
   p["hope"] := ["gav","jon","bob","abe","ian","dan","hal","ed","col","fred"]
   p["ivy"]  := ["ian","col","hal","gav","fred","bob","abe","ed","jon","dan"]
   p["jan"]  := ["ed","hal","gav","abe","bob","jon","col","ian","fred","dan"]
   
   return X
end

printf.icn provides formatting

Output:
Matching:
abi accepted abe's proposal
cath accepted bob's proposal
hope accepted col's proposal
ivy accepted dan's proposal
jan accepted ed's proposal
bea accepted fred's proposal
gay accepted gav's proposal
eve accepted hal's proposal
hope chose ian over col
abi chose jon over abe
dee accepted col's proposal
ivy chose abe over dan
fay accepted dan's proposal

Engagements:
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

Engagments are all stable.

Swapping abi and bea

Engagements:
abi is engaged to fred
bea is engaged to jon
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 of bea to fred is unstable.

J[edit]

Mraw=: ;: ;._2 noun define -. ':,'
  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
)

Fraw=: ;: ;._2 noun define -. ':,'
  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
)

GuyNames=: {."1 Mraw
GalNames=: {."1 Fraw
 
Mprefs=: GalNames i. }."1 Mraw
Fprefs=: GuyNames i. }."1 Fraw
 
propose=: dyad define
  engaged=. x
  'guy gal'=. y
  if. gal e. engaged do.
    fiance=. engaged i. gal
    if. guy <&((gal{Fprefs)&i.) fiance do.
      engaged=. gal guy} _ fiance} engaged
    end.
  else.
    engaged=. gal guy} engaged
  end.
  engaged
)
 
matchMake=: monad define
  engaged=. _"0 GuyNames NB. initially no one is engaged
  fallback=. 0"0 engaged NB. and each guy will first propose to his favorite
  whilst. _ e. engaged do.
    for_guy. I. _ = engaged do.
      next=. guy{fallback
      gal=. (<guy,next){Mprefs
      engaged=. engaged propose guy,gal
      fallback=. (next+1) guy} fallback
    end.
  end.
  GuyNames,:engaged{GalNames
)
 
checkStable=: monad define
  'guys gals'=. (GuyNames,:GalNames) i."1 y
  satisfied=. ] >: (<0 1) |: ]
  guyshappy=. satisfied (guys{Mprefs) i."1 0/ gals
  galshappy=. satisfied (gals{Fprefs) i."1 0/ guys
  unstable=. 4$.$.-. guyshappy +. |:galshappy
  if. bad=. 0 < #unstable do.
    smoutput 'Engagements preferred by both members to their current ones:'
    smoutput y {~"1 0"2 1 unstable
  end.
  assert-.bad
)

For most of this, males and females are both represented by indices. Rows of Mprefs are indexed by a male index and each contains a list female indices, in priority order. Rows of Fprefs are indexed by a female index and each contains a list male indices in priority order. These indices select the corresponding names from GuyNames and GalNames.

In matchMake (and propose), engaged identifies the gal each guy is engaged to (or _ if that guy is not engaged). And, fallback identifies the column which has the next gal, in Mprefs, for that guy to propose to.

Example use:

   matchMake ''
┌───┬────┬───┬───┬───┬────┬───┬───┬────┬───┐
abebob coldaned fredgavhalian jon
├───┼────┼───┼───┼───┼────┼───┼───┼────┼───┤
ivycathdeefayjanbea gayevehopeabi
└───┴────┴───┴───┴───┴────┴───┴───┴────┴───┘

Stability check:

   checkStable matchMake''

(no news is good news)

An altered result, and a stability check on it (showing what would happen for a bogus result):

   0 105 A."_1 matchMake ''  NB. swap abi and bea
┌───┬────┬───┬───┬───┬────┬───┬───┬────┬───┐
abebob coldaned fredgavhalian jon
├───┼────┼───┼───┼───┼────┼───┼───┼────┼───┤
ivycathdeefayjanabi gayevehopebea
└───┴────┴───┴───┴───┴────┴───┴───┴────┴───┘
   checkStable 0 105 A."_1 matchMake ''
Engagements preferred by both members to their current ones:
┌────┬───┐
fredbea
├────┼───┤
jon fay
├────┼───┤
jon gay
├────┼───┤
jon eve
└────┴───┘
|assertion failure: assert
|       assert-.bad

As an aside, note that the guys fared much better than the gals here, with over half of the guys getting their first preference and only one gal getting her first preference. The worst match for any guy was fourth preference where the worst for any gal was seventh preference.

Java[edit]

This is not a direct translation of Python, but it's fairly close (especially the stability check).

import java.util.*;

public class Stable {
    static List<String> guys = Arrays.asList(
            new String[]{
        "abe", "bob", "col", "dan", "ed", "fred", "gav", "hal", "ian", "jon"});
    static List<String> girls = Arrays.asList(
            new String[]{
        "abi", "bea", "cath", "dee", "eve", "fay", "gay", "hope", "ivy", "jan"});
    static Map<String, List<String>> guyPrefers =
            new HashMap<String, List<String>>(){{
        put("abe",
            Arrays.asList("abi", "eve", "cath", "ivy", "jan", "dee", "fay",
            "bea", "hope", "gay"));
        put("bob",
            Arrays.asList("cath", "hope", "abi", "dee", "eve", "fay", "bea",
            "jan", "ivy", "gay"));
        put("col",
            Arrays.asList("hope", "eve", "abi", "dee", "bea", "fay", "ivy",
            "gay", "cath", "jan"));
        put("dan",
            Arrays.asList("ivy", "fay", "dee", "gay", "hope", "eve", "jan",
            "bea", "cath", "abi"));
        put("ed",
            Arrays.asList("jan", "dee", "bea", "cath", "fay", "eve", "abi",
            "ivy", "hope", "gay"));
        put("fred",
            Arrays.asList("bea", "abi", "dee", "gay", "eve", "ivy", "cath",
            "jan", "hope", "fay"));
        put("gav",
            Arrays.asList("gay", "eve", "ivy", "bea", "cath", "abi", "dee",
            "hope", "jan", "fay"));
        put("hal",
            Arrays.asList("abi", "eve", "hope", "fay", "ivy", "cath", "jan",
            "bea", "gay", "dee"));
        put("ian",
            Arrays.asList("hope", "cath", "dee", "gay", "bea", "abi", "fay",
            "ivy", "jan", "eve"));
        put("jon",
            Arrays.asList("abi", "fay", "jan", "gay", "eve", "bea", "dee",
            "cath", "ivy", "hope"));
    }};
    static Map<String, List<String>> girlPrefers =
            new HashMap<String, List<String>>(){{
        put("abi",
            Arrays.asList("bob", "fred", "jon", "gav", "ian", "abe", "dan",
            "ed", "col", "hal"));
        put("bea",
            Arrays.asList("bob", "abe", "col", "fred", "gav", "dan", "ian",
            "ed", "jon", "hal"));
        put("cath",
            Arrays.asList("fred", "bob", "ed", "gav", "hal", "col", "ian",
            "abe", "dan", "jon"));
        put("dee",
            Arrays.asList("fred", "jon", "col", "abe", "ian", "hal", "gav",
            "dan", "bob", "ed"));
        put("eve",
            Arrays.asList("jon", "hal", "fred", "dan", "abe", "gav", "col",
            "ed", "ian", "bob"));
        put("fay",
            Arrays.asList("bob", "abe", "ed", "ian", "jon", "dan", "fred",
            "gav", "col", "hal"));
        put("gay",
            Arrays.asList("jon", "gav", "hal", "fred", "bob", "abe", "col",
            "ed", "dan", "ian"));
        put("hope",
            Arrays.asList("gav", "jon", "bob", "abe", "ian", "dan", "hal",
            "ed", "col", "fred"));
        put("ivy",
            Arrays.asList("ian", "col", "hal", "gav", "fred", "bob", "abe",
            "ed", "jon", "dan"));
        put("jan",
            Arrays.asList("ed", "hal", "gav", "abe", "bob", "jon", "col",
            "ian", "fred", "dan"));
    }};
    public static void main(String[] args){
        Map<String, String> matches = match(guys, guyPrefers, girlPrefers);
        for(Map.Entry<String, String> couple:matches.entrySet()){
            System.out.println(
                    couple.getKey() + " is engaged to " + couple.getValue());
        }
        if(checkMatches(guys, girls, matches, guyPrefers, girlPrefers)){
            System.out.println("Marriages are stable");
        }else{
            System.out.println("Marriages are unstable");
        }
        String tmp = matches.get(girls.get(0));
        matches.put(girls.get(0), matches.get(girls.get(1)));
        matches.put(girls.get(1), tmp);
        System.out.println(
                girls.get(0) +" and " + girls.get(1) + " have switched partners");
        if(checkMatches(guys, girls, matches, guyPrefers, girlPrefers)){
            System.out.println("Marriages are stable");
        }else{
            System.out.println("Marriages are unstable");
        }
    }

    private static Map<String, String> match(List<String> guys,
            Map<String, List<String>> guyPrefers,
            Map<String, List<String>> girlPrefers){
        Map<String, String> engagedTo = new TreeMap<String, String>();
        List<String> freeGuys = new LinkedList<String>();
        freeGuys.addAll(guys);
        while(!freeGuys.isEmpty()){
            String thisGuy = freeGuys.remove(0); //get a load of THIS guy
            List<String> thisGuyPrefers = guyPrefers.get(thisGuy);
            for(String girl:thisGuyPrefers){
                if(engagedTo.get(girl) == null){//girl is free
                    engagedTo.put(girl, thisGuy); //awww
                    break;
                }else{
                    String otherGuy = engagedTo.get(girl);
                    List<String> thisGirlPrefers = girlPrefers.get(girl);
                    if(thisGirlPrefers.indexOf(thisGuy) <
                            thisGirlPrefers.indexOf(otherGuy)){
                        //this girl prefers this guy to the guy she's engaged to
                        engagedTo.put(girl, thisGuy);
                        freeGuys.add(otherGuy);
                        break;
                    }//else no change...keep looking for this guy
                }
            }
        }
        return engagedTo;
    }

    private static boolean checkMatches(List<String> guys, List<String> girls,
            Map<String, String> matches, Map<String, List<String>> guyPrefers,
            Map<String, List<String>> girlPrefers) {
        if(!matches.keySet().containsAll(girls)){
            return false;
        }

        if(!matches.values().containsAll(guys)){
            return false;
        }

        Map<String, String> invertedMatches = new TreeMap<String, String>();
        for(Map.Entry<String, String> couple:matches.entrySet()){
            invertedMatches.put(couple.getValue(), couple.getKey());
        }

        for(Map.Entry<String, String> couple:matches.entrySet()){
            List<String> shePrefers = girlPrefers.get(couple.getKey());
            List<String> sheLikesBetter = new LinkedList<String>();
            sheLikesBetter.addAll(shePrefers.subList(0, shePrefers.indexOf(couple.getValue())));
            List<String> hePrefers = guyPrefers.get(couple.getValue());
            List<String> heLikesBetter = new LinkedList<String>();
            heLikesBetter.addAll(hePrefers.subList(0, hePrefers.indexOf(couple.getKey())));

            for(String guy : sheLikesBetter){
                String guysFinace = invertedMatches.get(guy);
                List<String> thisGuyPrefers = guyPrefers.get(guy);
                if(thisGuyPrefers.indexOf(guysFinace) >
                        thisGuyPrefers.indexOf(couple.getKey())){
                    System.out.printf("%s likes %s better than %s and %s"
                            + " likes %s better than their current partner\n",
                       couple.getKey(), guy, couple.getValue(),
                       guy, couple.getKey());
                    return false;
                }
            }

            for(String girl : heLikesBetter){
                String girlsFinace = matches.get(girl);
                List<String> thisGirlPrefers = girlPrefers.get(girl);
                if(thisGirlPrefers.indexOf(girlsFinace) >
                        thisGirlPrefers.indexOf(couple.getValue())){
                    System.out.printf("%s likes %s better than %s and %s"
                            + " likes %s better than their current partner\n",
                       couple.getValue(), girl, couple.getKey(),
                       girl, couple.getValue());
                    return false;
                }
            }
        }
        return true;
    }
}
Output:
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
Marriages are stable
abi and bea have switched partners
fred likes bea better than abi and bea likes fred better than their current partner
Marriages are unstable

JavaScript[edit]

function Person(name) {

    var candidateIndex = 0;

    this.name = name;
    this.fiance = null;
    this.candidates = [];

    this.rank = function(p) {
        for (i = 0; i < this.candidates.length; i++)
            if (this.candidates[i] === p) return i;
        return this.candidates.length + 1;
    }

    this.prefers = function(p) {
        return this.rank(p) < this.rank(this.fiance);
    }

    this.nextCandidate = function() {
        if (candidateIndex >= this.candidates.length) return null;
        return this.candidates[candidateIndex++];
    }

    this.engageTo = function(p) {
        if (p.fiance) p.fiance.fiance = null;
        p.fiance = this;
        if (this.fiance) this.fiance.fiance = null;
        this.fiance = p;
    }

    this.swapWith = function(p) {
        console.log("%s & %s swap partners", this.name, p.name);
        var thisFiance = this.fiance;
        var pFiance = p.fiance;
        this.engageTo(pFiance);
        p.engageTo(thisFiance);
    }
}

function isStable(guys, gals) {
    for (var i = 0; i < guys.length; i++)
        for (var j = 0; j < gals.length; j++)
            if (guys[i].prefers(gals[j]) && gals[j].prefers(guys[i]))
                return false;
    return true;
}

function engageEveryone(guys) {
    var done;
    do {
        done = true;
        for (var i = 0; i < guys.length; i++) {
            var guy = guys[i];
            if (!guy.fiance) {
                done = false;
                var gal = guy.nextCandidate();
                if (!gal.fiance || gal.prefers(guy))
                    guy.engageTo(gal);
            }
        }
    } while (!done);
}

function doMarriage() {

    var abe  = new Person("Abe");
    var bob  = new Person("Bob");
    var col  = new Person("Col");
    var dan  = new Person("Dan");
    var ed   = new Person("Ed");
    var fred = new Person("Fred");
    var gav  = new Person("Gav");
    var hal  = new Person("Hal");
    var ian  = new Person("Ian");
    var jon  = new Person("Jon");
    var abi  = new Person("Abi");
    var bea  = new Person("Bea");
    var cath = new Person("Cath");
    var dee  = new Person("Dee");
    var eve  = new Person("Eve");
    var fay  = new Person("Fay");
    var gay  = new Person("Gay");
    var hope = new Person("Hope");
    var ivy  = new Person("Ivy");
    var jan  = new Person("Jan");

    abe.candidates  = [abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay];
    bob.candidates  = [cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay];
    col.candidates  = [hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan];
    dan.candidates  = [ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi];
    ed.candidates   = [jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay];
    fred.candidates = [bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay];
    gav.candidates  = [gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay];
    hal.candidates  = [abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee];
    ian.candidates  = [hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve];
    jon.candidates  = [abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope];
    abi.candidates  = [bob, fred, jon, gav, ian, abe, dan, ed, col, hal];
    bea.candidates  = [bob, abe, col, fred, gav, dan, ian, ed, jon, hal];
    cath.candidates = [fred, bob, ed, gav, hal, col, ian, abe, dan, jon];
    dee.candidates  = [fred, jon, col, abe, ian, hal, gav, dan, bob, ed];
    eve.candidates  = [jon, hal, fred, dan, abe, gav, col, ed, ian, bob];
    fay.candidates  = [bob, abe, ed, ian, jon, dan, fred, gav, col, hal];
    gay.candidates  = [jon, gav, hal, fred, bob, abe, col, ed, dan, ian];
    hope.candidates = [gav, jon, bob, abe, ian, dan, hal, ed, col, fred];
    ivy.candidates  = [ian, col, hal, gav, fred, bob, abe, ed, jon, dan];
    jan.candidates  = [ed, hal, gav, abe, bob, jon, col, ian, fred, dan];

    var guys = [abe, bob, col, dan, ed, fred, gav, hal, ian, jon];
    var gals = [abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan];

    engageEveryone(guys);

    for (var i = 0; i < guys.length; i++) {
        console.log("%s is engaged to %s", guys[i].name, guys[i].fiance.name);
    }
    console.log("Stable = %s", isStable(guys, gals) ? "Yes" : "No");
    jon.swapWith(fred);
    console.log("Stable = %s", isStable(guys, gals) ? "Yes" : "No");
}

doMarriage();
Output:
Abe is engaged to Ivy
Bob is engaged to Cath
Col is engaged to Dee
Dan is engaged to Fay
Ed is engaged to Jan
Fred is engaged to Bea
Gav is engaged to Gay
Hal is engaged to Eve
Ian is engaged to Hope
Jon is engaged to Abi
Stable = Yes
Jon & Fred swap partners
Stable = No

jq[edit]

Adapted from Wren

Works with: jq

Also works with gojq, the Go implementation of jq

Also works with fq, a Go implementation of a large subset of jq

This adaptation from #Wren illustrates how jq's `debug` facility can be used to show details about the progress of a computation. These progress messages could be suppressed, for example, by redefining debug/1 as: `def debug(msg): .;`

# Generic utilities:
def debug(msg): (msg|debug) as $_ | .;

# Remove the key named $key from an object specified by the given path
def rmkey($key; path):
  path |= with_entries(select(.key != $key));

def printPairs:
  to_entries[]
  | "\(.key) \(.value)";

def debugPairs:
  . as $in
  | reduce to_entries[] as $x (null;
      $x | debug("\(.key) \(.value)") )
  | $in;

# The individual preferences
def mPref : {
    "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"]
};
 
def wPref : {
    "abi": {
        "bob": 1, "fred": 2, "jon": 3, "gav": 4, "ian": 5,
        "abe": 6, "dan": 7, "ed": 8, "col": 9, "hal": 10},
    "bea": {
        "bob": 1, "abe": 2, "col": 3, "fred": 4, "gav": 5,
        "dan": 6, "ian": 7, "ed": 8, "jon": 9, "hal": 10},
    "cath": {
        "fred": 1, "bob": 2, "ed": 3, "gav": 4, "hal": 5,
        "col": 6, "ian": 7, "abe": 8, "dan": 9, "jon": 10},
    "dee": {
        "fred": 1, "jon": 2, "col": 3, "abe": 4, "ian": 5,
        "hal": 6, "gav": 7, "dan": 8, "bob": 9, "ed": 10},
    "eve": {
        "jon": 1, "hal": 2, "fred": 3, "dan": 4, "abe": 5,
        "gav": 6, "col": 7, "ed": 8, "ian": 9, "bob": 10},
    "fay": {
        "bob": 1, "abe": 2, "ed": 3, "ian": 4, "jon": 5,
        "dan": 6, "fred": 7, "gav": 8, "col": 9, "hal": 10},
    "gay": {
        "jon": 1, "gav": 2, "hal": 3, "fred": 4, "bob": 5,
        "abe": 6, "col": 7, "ed": 8, "dan": 9, "ian": 10},
    "hope": {
        "gav": 1, "jon": 2, "bob": 3, "abe": 4, "ian": 5,
        "dan": 6, "hal": 7, "ed": 8, "col": 9, "fred": 10},
    "ivy": {
        "ian": 1, "col": 2, "hal": 3, "gav": 4, "fred": 5,
        "bob": 6, "abe": 7, "ed": 8, "jon": 9, "dan": 10},
    "jan": {
        "ed": 1, "hal": 2, "gav": 3, "abe": 4, "bob": 5,
        "jon": 6, "col": 7, "ian": 8, "fred": 9, "dan": 10}
};

# pair/2 implements the Gale/Shapley algorithm.
# $pPref gives the proposer preferences (like mPref above)
# $rPref gives the recipient preferences (like wPref above)
# Output: a JSON object giving the matching as w:m pairs
def pair($pPref; $rPref):

  def undo:
    debug("engagement: \(.recipient) \(.proposer)")
    | .proposals[.recipient] = {proposer, pPref: .ppref, rPref: .rpref}
    | rmkey(.proposer; .pFree)
    | rmkey(.recipient; .rFree);

  # preferences must be saved in case engagement is broken;
  # they will be saved as: {proposer, pPref, rPref}
  { pFree: $pPref,
    rFree: $rPref,
    proposals: {} # key is recipient (w)
  }
  # WP pseudocode comments prefaced with WP: m is proposer, w is recipient.
  # WP: while ∃ free man m who still has a woman w to propose to
  | until (.pFree|length == 0;  # while there is a free proposer ...
      # pick a proposer
      (.pFree|to_entries[0]) as $me
      | .proposer = $me.key
      | .ppref    = $me.value
      | if .ppref|length == 0
        then .  # if proposer has no possible recipients, skip
        # WP: w = m's highest ranked woman to whom he has not yet proposed
        else
          .recipient = .ppref[0]   # highest ranked is first in list
          | .ppref = .ppref[1:]    # pop from list
          # WP: if w is free
          | .rpref = .rFree[.recipient]
          | if .rpref
            then # WP: (m, w) become engaged
	      undo
            else 
              # WP: else some pair (m', w) already exists
              .s = .proposals[.recipient]  # get proposal saved preferences
              # WP: if w prefers m to m'
              | if .s.rPref[.proposer] < .s.rPref[.s.proposer]
                then debug("engagement broken: \(.recipient) \(.s.proposer)")
                  # WP: m' becomes free
                  | .pFree[.s.proposer] = .s.pPref # return proposer to the map
                  # WP: (m, w) become engaged
                  | .rpref = .s.rPref
		  | undo
                else 
                  # WP: else (m', w) remain engaged
                  .pFree[.proposer] = .ppref # update preferences in map
                end
	    end
          end
    )  # end until
    # construct return value
    | reduce (.proposals|to_entries)[] as $me ({};
        .[$me.key] = $me.value.proposer ) ;

# return {result, emit} where .emit is an explanation
def determineStability($ps; $pPref; $rPref):
  $ps
  | debug("Determining the stability of the following pairings:")
  | debugPairs
  | to_entries as $pse
  | {i:0}
  | until(.emit or .i == ($ps|length);  # stop after detecting an instability
        $pse[.i].key   as $r
      | $pse[.i].value as $p
      | (first($pPref[$p][] as $rp
               | if ($r == $rp) then false
                 else $rPref[$rp] as $rprefs
                 | if ($rprefs[$p] < $rprefs[$ps[$rp]])
                   then "\ncauses instability because " +
                        "\($p) and \($rp) would prefer each other over their current pairings."
                   else empty
                   end
                 end ) // false) as $counterexample
        | if $counterexample == false then . else .emit = $counterexample end
      | .i += 1 )
  | if .emit then {result: false, emit} else {result: true} end ;

# Determine pairings using the Gale/Shapley algorithm and then perturb until instability arises.
def task:
  pair(mPref; wPref)
  | . as $ps
  | "Solution:", printPairs,
    # verify
    ((determineStability($ps; mPref; wPref)) as $return
     | ($return.emit // empty ),
       if $return.result == false
       then debug("invalid input")
       else
       "The result has been validated.",
       "Now perturb the result until validation fails.",
        (label $done
         | foreach range(0; $ps|length -1 ) as $start (.;
           .ps = $ps 
           | (.ps|to_entries) as $kv
           | .w2[0] = $kv[$start].key
           | .m2[0] = $kv[$start].value
           | .w2[1] = $kv[$start+1].key
           | .m2[1] = $kv[$start+1].value
           | .emit = "\nExchanging partners of \(.m2[0]) and \(.m2[1])"
           | .ps[.w2[0]] = .m2[1]
           | .ps[.w2[1]] = .m2[0]
           # validate perturbed pairings
           | determineStability(.ps; mPref; wPref) as $result
           | .emit += $result.emit
           | .result = $result.result
           ;
           .emit,
           if .result == false then break $done else empty end
          ))
       end );

task
Output:

Invocation: jq -nr -f stable-marriage-problem.jq

["DEBUG:","engagement: abi abe"]
["DEBUG:","engagement: cath bob"]
["DEBUG:","engagement: hope col"]
["DEBUG:","engagement: ivy dan"]
["DEBUG:","engagement: jan ed"]
["DEBUG:","engagement: bea fred"]
["DEBUG:","engagement: gay gav"]
["DEBUG:","engagement: eve hal"]
["DEBUG:","engagement broken: hope col"]
["DEBUG:","engagement: hope ian"]
["DEBUG:","engagement broken: abi abe"]
["DEBUG:","engagement: abi jon"]
["DEBUG:","engagement: dee col"]
["DEBUG:","engagement broken: ivy dan"]
["DEBUG:","engagement: ivy abe"]
["DEBUG:","engagement: fay dan"]
Solution:
abi jon
cath bob
hope ian
ivy abe
jan ed
bea fred
gay gav
eve hal
dee col
fay dan
["DEBUG:","Determining the stability of the following pairings:"]
["DEBUG:","abi jon"]
["DEBUG:","cath bob"]
["DEBUG:","hope ian"]
["DEBUG:","ivy abe"]
["DEBUG:","jan ed"]
["DEBUG:","bea fred"]
["DEBUG:","gay gav"]
["DEBUG:","eve hal"]
["DEBUG:","dee col"]
["DEBUG:","fay dan"]
The result has been validated.
Now perturb the result until validation fails.
["DEBUG:","Determining the stability of the following pairings:"]
["DEBUG:","abi bob"]
["DEBUG:","cath jon"]
["DEBUG:","hope ian"]
["DEBUG:","ivy abe"]
["DEBUG:","jan ed"]
["DEBUG:","bea fred"]
["DEBUG:","gay gav"]
["DEBUG:","eve hal"]
["DEBUG:","dee col"]
["DEBUG:","fay dan"]

Exchanging partners of jon and bob
causes instability because bob and cath would prefer each other over their current pairings.


Julia[edit]

# This is not optimized, but tries to follow the pseudocode given the Wikipedia entry below.
# Reference: https://en.wikipedia.org/wiki/Stable_marriage_problem#Algorithm

const males = ["abe", "bob", "col", "dan", "ed", "fred", "gav", "hal", "ian", "jon"]
const females = ["abi", "bea", "cath", "dee", "eve", "fay", "gay", "hope", "ivy", "jan"]

const malepreferences = Dict(
  "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"]
)

const femalepreferences = Dict(
  "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"]
)

function pshuf(d)
    ret = Dict()
    for (k,v) in d
        ret[k] = shuffle(v)
    end
    ret
end

# helper functions for the verb: p1 "prefers" p2 over p3
pindexin(a, p) = ([i for i in 1:length(a) if a[i] == p])[1]
prefers(d, p1, p2, p3) = (pindexin(d[p1], p2) < pindexin(d[p1], p3))

function isstable(mmatchup, fmatchup, mpref, fpref)
    for (mmatch, fmatch) in mmatchup
        for f in mpref[mmatch]
            if(f != fmatch && prefers(mpref, mmatch, f, fmatch)
                           && prefers(fpref, f, mmatch, fmatchup[f]))
                println("$mmatch prefers $f and $f prefers $mmatch over their current partners.")
                return false
            end
        end
    end
    true
end

function galeshapley(men, women, malepref, femalepref)
    # Initialize all m ∈ M and w ∈ W to free
    mfree = Dict([(p, true) for p in men])
    wfree = Dict([(p, true) for p in women])
    mpairs = Dict()
    wpairs = Dict()
    while true                    # while ∃ free man m who still has a woman w to propose to
        bachelors = [p for p in keys(mfree) if mfree[p]]
        if(length(bachelors) == 0)
            return mpairs, wpairs
        end
        for m in bachelors
            for w in malepref[m]  # w = first woman on m’s list to whom m has not yet proposed
                if(wfree[w])      # if w is free (else some pair (m', w) already exists)
                    #println("Free match: $m, $w")
                    mpairs[m] = w # (m, w) become engaged
                    wpairs[w] = m # double entry bookeeping
                    mfree[m] = false
                    wfree[w] = false
                    break
                elseif(prefers(femalepref, w, m, wpairs[w])) # if w prefers m to m'
                    #println("Unmatch $(wpairs[w]), match: $m, $w")
                    mfree[wpairs[w]] = true # m' becomes free
                    mpairs[m] = w           # (m, w) become engaged
                    wpairs[w] = m
                    mfree[m] = false
                    break
                end                         # else (m', w) remain engaged, so continue
            end
        end
    end
end

function tableprint(txt, ans, stab)
    println(txt)
    println("   Man     Woman")
    println("   -----   -----")
    show(STDOUT, "text/plain", ans)
    if(stab)
        println("\n  ----STABLE----\n\n")
    else
        println("\n  ---UNSTABLE---\n\n")
    end
end

println("Use the Gale Shapley algorithm to find a stable set of engagements.")
answer = galeshapley(males, females, malepreferences, femalepreferences)
stabl = isstable(answer[1], answer[2], malepreferences, femalepreferences)
tableprint("Original Data Table", answer[1], stabl)

println("To check this is not a one-off solution, run the function on a randomized sample.")
newmpref = pshuf(malepreferences)
newfpref = pshuf(femalepreferences)
answer = galeshapley(males, females, newmpref, newfpref)
stabl = isstable(answer[1], answer[2], newmpref, newfpref)
tableprint("Shuffled Preferences", answer[1], stabl)

# trade abe with bob
println("Perturb this set of engagements to form an unstable set of engagements then check this new set for stability.")
answer = galeshapley(males, females, malepreferences, femalepreferences)
fia1 = (answer[1])["abe"]
fia2 = (answer[1])["bob"]
answer[1]["abe"] = fia2
answer[1]["bob"] = fia1
answer[2][fia1] = "bob"
answer[2][fia2] = "abe"
stabl = isstable(answer[1], answer[2], malepreferences, femalepreferences)
tableprint("Original Data With Bob and Abe Switched", answer[1], stabl)
Output:
Use the Gale Shapley algorithm to find a stable set of engagements.
Original Data Table
   Man     Woman
   -----   -----
Dict{Any,Any} with 10 entries:
  "bob" => "cath"
  "dan" => "fay"
  "fred" => "bea"
  "jon" => "abi"
  "ian" => "hope"
  "gav" => "gay"
  "ed" => "jan"
  "col" => "dee"
  "hal" => "eve"
  "abe" => "ivy"
  ----STABLE----


To check this is not a one-off solution, run the function on a randomized sample.
Shuffled Preferences
   Man     Woman
   -----   -----
Dict{Any,Any} with 10 entries:
  "bob" => "abi"
  "dan" => "bea"
  "fred" => "jan"
  "jon" => "dee"
  "ian" => "fay"
  "gav" => "ivy"
  "ed" => "gay"
  "col" => "cath"
  "hal" => "hope"
  "abe" => "eve"
  ----STABLE----


Perturb this set of engagements to form an unstable set of engagements then check this new set for stability.
bob prefers cath and cath prefers bob over their current partners.
Original Data With Bob and Abe Switched
   Man     Woman
   -----   -----
Dict{Any,Any} with 10 entries:
  "bob" => "ivy"
  "dan" => "fay"
  "fred" => "bea"
  "jon" => "abi"
  "ian" => "hope"
  "gav" => "gay"
  "ed" => "jan"
  "col" => "dee"
  "hal" => "eve"
  "abe" => "cath"
  ---UNSTABLE---

Kotlin[edit]

data class Person(val name: String) {
    val preferences = mutableListOf<Person>()
    var matchedTo: Person? = null

    fun trySwap(p: Person) {
        if (prefers(p)) {
            matchedTo?.matchedTo = null
            matchedTo = p
            p.matchedTo = this
        }
    }

    fun prefers(p: Person) = when (matchedTo) {
        null -> true
        else -> preferences.indexOf(p) < preferences.indexOf(matchedTo!!)
    }

    fun showMatch() = "$name <=> ${matchedTo?.name}"
}

fun match(males: Collection<Person>) {
    while (males.find { it.matchedTo == null }?.also { match(it) } != null) {
    }
}

fun match(male: Person) {
    while (male.matchedTo == null) {
        male.preferences.removeAt(0).trySwap(male)
    }
}

fun isStableMatch(males: Collection<Person>, females: Collection<Person>): Boolean {
    return males.all { isStableMatch(it, females) }
}

fun isStableMatch(male: Person, females: Collection<Person>): Boolean {

    val likesBetter = females.filter { !male.preferences.contains(it) }
    val stable = !likesBetter.any { it.prefers(male) }

    if (!stable) {
        println("#### Unstable pair: ${male.showMatch()}")
    }
    return stable
}


fun main(args: Array<String>) {
    val inMales = mapOf(
            "abe" to mutableListOf("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
            "bob" to mutableListOf("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
            "col" to mutableListOf("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
            "dan" to mutableListOf("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"),
            "ed" to mutableListOf("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"),
            "fred" to mutableListOf("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"),
            "gav" to mutableListOf("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"),
            "hal" to mutableListOf("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"),
            "ian" to mutableListOf("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
            "jon" to mutableListOf("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"))

    val inFemales = mapOf(
            "abi" to listOf("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
            "bea" to listOf("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
            "cath" to listOf("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
            "dee" to listOf("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"),
            "eve" to listOf("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"),
            "fay" to listOf("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"),
            "gay" to listOf("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"),
            "hope" to listOf("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"),
            "ivy" to listOf("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
            "jan" to listOf("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"))


    fun buildPrefs(person: Person, stringPrefs: List<String>, population: List<Person>) {
        person.preferences.addAll(
                stringPrefs.map { name -> population.single { it.name == name } }
        )
    }

    val males = inMales.keys.map { Person(it) }
    val females = inFemales.keys.map { Person(it) }

    males.forEach { buildPrefs(it, inMales[it.name]!!, females) }
    females.forEach { buildPrefs(it, inFemales[it.name]!!, males) }


    match(males)
    males.forEach { println(it.showMatch()) }
    println("#### match is stable: ${isStableMatch(males, females)}")


    fun swapMatch(male1: Person, male2: Person) {
        val female1 = male1.matchedTo!!
        val female2 = male2.matchedTo!!

        male1.matchedTo = female2
        male2.matchedTo = female1

        female1.matchedTo = male2
        female2.matchedTo = male1
    }

    swapMatch(males.single { it.name == "fred" }, males.single { it.name == "jon" })
    males.forEach { println(it.showMatch()) }
    println("#### match is stable: ${isStableMatch(males, females)}")
}
Output:
abe <=> ivy
bob <=> cath
col <=> dee
dan <=> fay
ed <=> jan
fred <=> bea
gav <=> gay
hal <=> eve
ian <=> hope
jon <=> abi
##### match is stable: true
abe <=> ivy
bob <=> cath
col <=> dee
dan <=> fay
ed <=> jan
fred <=> abi
gav <=> gay
hal <=> eve
ian <=> hope
jon <=> bea
#### Unstable pair: fred <=> abi
##### match is stable: false

Lua[edit]

Translation of: C#
local Person = {}
Person.__index = Person

function Person.new(inName)
    local o = {
        name            = inName,
        prefs           = nil,
        fiance          = nil,
        _candidateIndex = 1,
    }
    return setmetatable(o, Person)
end

function Person:indexOf(other)
    for i, p in pairs(self.prefs) do
        if p == other then return i end
    end
    return 999
end

function Person:prefers(other)
    return self:indexOf(other) < self:indexOf(self.fiance)
end

function Person:nextCandidateNotYetProposedTo()
    if self._candidateIndex >= #self.prefs then return nil end
    local c = self.prefs[self._candidateIndex];
    self._candidateIndex = self._candidateIndex + 1
    return c;
end

function Person:engageTo(other)
    if other.fiance then
        other.fiance.fiance = nil
    end
    other.fiance = self
    if self.fiance then
        self.fiance.fiance = nil
    end
    self.fiance = other;
end

local function isStable(men)
    local women = men[1].prefs
    local stable = true
    for _, guy in pairs(men) do
        for _, gal in pairs(women) do
            if guy:prefers(gal) and gal:prefers(guy) then
                stable = false
                print(guy.name .. ' and ' .. gal.name ..
                      ' prefer each other over their partners ' ..
                      guy.fiance.name .. ' and ' .. gal.fiance.name)
            end
        end
    end
    return stable
end

local abe  = Person.new("Abe")
local bob  = Person.new("Bob")
local col  = Person.new("Col")
local dan  = Person.new("Dan")
local ed   = Person.new("Ed")
local fred = Person.new("Fred")
local gav  = Person.new("Gav")
local hal  = Person.new("Hal")
local ian  = Person.new("Ian")
local jon  = Person.new("Jon")

local abi  = Person.new("Abi")
local bea  = Person.new("Bea")
local cath = Person.new("Cath")
local dee  = Person.new("Dee")
local eve  = Person.new("Eve")
local fay  = Person.new("Fay")
local gay  = Person.new("Gay")
local hope = Person.new("Hope")
local ivy  = Person.new("Ivy")
local jan  = Person.new("Jan")

abe.prefs  = { abi,  eve,  cath, ivy,  jan,  dee,  fay,  bea,  hope, gay  }
bob.prefs  = { cath, hope, abi,  dee,  eve,  fay,  bea,  jan,  ivy,  gay  }
col.prefs  = { hope, eve,  abi,  dee,  bea,  fay,  ivy,  gay,  cath, jan  }
dan.prefs  = { ivy,  fay,  dee,  gay,  hope, eve,  jan,  bea,  cath, abi  }
ed.prefs   = { jan,  dee,  bea,  cath, fay,  eve,  abi,  ivy,  hope, gay  }
fred.prefs = { bea,  abi,  dee,  gay,  eve,  ivy,  cath, jan,  hope, fay  }
gav.prefs  = { gay,  eve,  ivy,  bea,  cath, abi,  dee,  hope, jan,  fay  }
hal.prefs  = { abi,  eve,  hope, fay,  ivy,  cath, jan,  bea,  gay,  dee  }
ian.prefs  = { hope, cath, dee,  gay,  bea,  abi,  fay,  ivy,  jan,  eve  }
jon.prefs  = { abi,  fay,  jan,  gay,  eve,  bea,  dee,  cath, ivy,  hope }

abi.prefs  = { bob,  fred, jon,  gav,  ian,  abe,  dan,  ed,   col,  hal  }
bea.prefs  = { bob,  abe,  col,  fred, gav,  dan,  ian,  ed,   jon,  hal  }
cath.prefs = { fred, bob,  ed,   gav,  hal,  col,  ian,  abe,  dan,  jon  }
dee.prefs  = { fred, jon,  col,  abe,  ian,  hal,  gav,  dan,  bob,  ed   }
eve.prefs  = { jon,  hal,  fred, dan,  abe,  gav,  col,  ed,   ian,  bob  }
fay.prefs  = { bob,  abe,  ed,   ian,  jon,  dan,  fred, gav,  col,  hal  }
gay.prefs  = { jon,  gav,  hal,  fred, bob,  abe,  col,  ed,   dan,  ian  }
hope.prefs = { gav,  jon,  bob,  abe,  ian,  dan,  hal,  ed,   col,  fred }
ivy.prefs  = { ian,  col,  hal,  gav,  fred, bob,  abe,  ed,   jon,  dan  }
jan.prefs  = { ed,   hal,  gav,  abe,  bob,  jon,  col,  ian,  fred, dan  }

local men = abi.prefs
local freeMenCount = #men
while freeMenCount > 0 do
    for _, guy in pairs(men) do
        if not guy.fiance then
            local gal = guy:nextCandidateNotYetProposedTo()
            if not gal.fiance then
                guy:engageTo(gal)
                freeMenCount = freeMenCount - 1
            elseif gal:prefers(guy) then
                guy:engageTo(gal)
            end
        end
    end
end

print(' ')
for _, guy in pairs(men) do
    print(guy.name .. ' is engaged to ' .. guy.fiance.name)
end
print('Stable: ', isStable(men))

print(' ')
print('Switching ' .. fred.name .. "'s & " .. jon.name .. "'s partners")
jon.fiance, fred.fiance = fred.fiance, jon.fiance
print('Stable: ', isStable(men))
Output:
Bob is engaged to Cath
Fred is engaged to Bea
Jon is engaged to Abi
Gav is engaged to Gay
Ian is engaged to Hope
Abe is engaged to Ivy
Dan is engaged to Fay
Ed is engaged to Jan
Col is engaged to Dee
Hal is engaged to Eve
Stable:   true

Switching Fred's & Jon's partners
Jon and Eve prefer each other over their partners Bea and Hal
Jon and Fay prefer each other over their partners Bea and Dan
Jon and Gay prefer each other over their partners Bea and Gav
Stable:   false

Mathematica / Wolfram Language[edit]

<<Combinatorica`;
ClearAll[CheckStability]
CheckStabilityHelp[male_, female_, ml_List, fl_List, pairing_List] := Module[{prefs, currentmale},
  prefs = fl[[female]];
  currentmale = Sort[Reverse /@ pairing][[female, 2]];
  FirstPosition[prefs, currentmale][[1]] < FirstPosition[prefs, male][[1]]
 ]
CheckStabilityHelp[male_, ml_List, fl_List, pairing_List] := Module[{prefs, m, f, p, otherf, reversepair, pos, othermen},
  prefs = ml[[male]];
  {m, f} = pairing[[male]];
  p = FirstPosition[prefs, f][[1]];
  otherf = Take[prefs, p - 1];
  AllTrue[otherf, CheckStabilityHelp[male, #, ml, fl, pairing] &]
 ]
CheckStability[ml_List, fl_List, pairing_List] := AllTrue[pairing[[All, 1]], CheckStabilityHelp[#, ml, fl, pairing] &]
males = {"abe", "bob", "col", "dan", "ed", "fred", "gav", "hal", 
   "ian", "jon"};
females = {"abi", "bea", "cath", "dee", "eve", "fay", "gay", "hope", 
   "ivy", "jan"};
ml = {{"abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", 
    "hope", "gay"}, {"cath", "hope", "abi", "dee", "eve", "fay", 
    "bea", "jan", "ivy", "gay"}, {"hope", "eve", "abi", "dee", "bea", 
    "fay", "ivy", "gay", "cath", "jan"}, {"ivy", "fay", "dee", "gay", 
    "hope", "eve", "jan", "bea", "cath", "abi"}, {"jan", "dee", "bea",
     "cath", "fay", "eve", "abi", "ivy", "hope", "gay"}, {"bea", 
    "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", 
    "fay"}, {"gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope",
     "jan", "fay"}, {"abi", "eve", "hope", "fay", "ivy", "cath", 
    "jan", "bea", "gay", "dee"}, {"hope", "cath", "dee", "gay", "bea",
     "abi", "fay", "ivy", "jan", "eve"}, {"abi", "fay", "jan", "gay", 
    "eve", "bea", "dee", "cath", "ivy", "hope"}};
fl = {{"bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", 
    "hal"}, {"bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", 
    "jon", "hal"}, {"fred", "bob", "ed", "gav", "hal", "col", "ian", 
    "abe", "dan", "jon"}, {"fred", "jon", "col", "abe", "ian", "hal", 
    "gav", "dan", "bob", "ed"}, {"jon", "hal", "fred", "dan", "abe", 
    "gav", "col", "ed", "ian", "bob"}, {"bob", "abe", "ed", "ian", 
    "jon", "dan", "fred", "gav", "col", "hal"}, {"jon", "gav", "hal", 
    "fred", "bob", "abe", "col", "ed", "dan", "ian"}, {"gav", "jon", 
    "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"}, {"ian", 
    "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", 
    "dan"}, {"ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", 
    "fred", "dan"}};
ml = ml /. Thread[females -> Range[Length[males]]];
fl = fl /. Thread[males -> Range[Length[females]]];
pairing = StableMarriage[ml, fl];
pairing = {Range[Length[pairing]], pairing} // Transpose;
pairing
CheckStability[ml, fl, pairing]
pairing[[{2, 7}, 2]] //= Reverse;
pairing
CheckStability[ml, fl, pairing]
Output:
{{1,9},{2,3},{3,4},{4,6},{5,10},{6,2},{7,7},{8,5},{9,8},{10,1}}
True
{{1,9},{2,7},{3,4},{4,6},{5,10},{6,2},{7,3},{8,5},{9,8},{10,1}}
False

Nim[edit]

import sequtils, random, strutils

const
  Pairs = 10
  MNames = ["abe", "bob", "col", "dan", "ed", "fred", "gav", "hal", "ian", "jon"]
  FNames = ["abi", "bea", "cath", "dee", "eve", "fay", "gay", "hope", "ivy", "jan"]
  MPreferences = [
    ["abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"],
    ["cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"],
    ["hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"],
    ["ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"],
    ["jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"],
    ["bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"],
    ["gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"],
    ["abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"],
    ["hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"],
    ["abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"]
  ]
  FPreferences = [
    ["bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"],
    ["bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"],
    ["fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"],
    ["fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"],
    ["jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"],
    ["bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"],
    ["jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"],
    ["gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"],
    ["ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"],
    ["ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"]
  ]

# recipient's preferences hold the preference score for each contender's id
func getRecPreferences[N: static int](prefs: array[N, array[N, string]],
    names: openArray[string]): array[N, array[N, int]] {.compileTime.} =
  for r, prefArray in pairs(prefs):
    for c, contender in pairs(prefArray):
      result[r][c] = prefArray.find(MNames[c])

# contender's preferences hold the recipient ids in descending order of preference
func getContPreferences[N: static int](prefs: array[N, array[N, string]],
     names: openArray[string]): array[N, array[N, int]] {.compileTime.} =
  for c, pref_seq in pairs(prefs):
    for r, pref in pairs(pref_seq):
      result[c][r] = names.find(pref)

const
  RecipientPrefs = getRecPreferences(FPreferences, MNames)
  ContenderPrefs = getContPreferences(MPreferences, FNames)

proc printCoupleNames(contPairs: seq[int]) =
  for c, r in pairs(contPairs):
    echo MNames[c] & " 💑 " & FNames[contPairs[c]]

func pair(): (seq[int], seq[int]) =
  # double booking to avoid inverse lookup using find
  var
    recPairs = newSeqWith(10, -1)
    contPairs = newSeqWith(10, -1)
  template engage(c, r: int) =
    #echo FNames[r] & " accepted " & MNames[c]
    contPairs[c] = r
    recPairs[r] = c
  var contQueue = newSeqWith(10, 0)
  while contPairs.contains(-1):
    for c in 0..<Pairs:
      if contPairs[c] == -1:
        let r = ContenderPrefs[c][contQueue[c]] #proposing to first in queue
        contQueue[c] += 1 #increment contender's queue for following iterations
        let curPair = recPairs[r] # current pair's index or -1 = vacant
        if curPair == -1:
          engage(c, r)
        # contender is more preferable than current
        elif RecipientPrefs[r][c] < RecipientPrefs[r][curPair]:
          contPairs[curPair] = -1 # vacate current pair
          #echo MNames[curPair] & " was dumped by " & FNames[r]
          engage(c, r)
  result = (contPairs, recPairs)

proc randomPair(max: int): (int, int) =
  let a = rand(max)
  var b = rand(max - 1)
  if b == a:
    b = max
  result = (a, b)

proc perturbPairs(contPairs, recPairs: var seq[int]) =
  randomize()
  let (a, b) = randomPair(Pairs-1)
  echo("Swapping ", MNames[a], " & ", MNames[b], " partners")
  swap(contPairs[a], contPairs[b])
  swap(recPairs[contPairs[a]], recPairs[contPairs[b]])

proc checkPairStability(contPairs, recPairs: seq[int]): bool =
  for c in 0..<Pairs: # each contender
    let curPairScore = ContenderPrefs[c].find(contPairs[c]) # pref. score for current pair
    for preferredRec in 0..<curPairScore: # try every recipient with higher score
      let
        checkedRec = ContenderPrefs[c][preferredRec]
        curRecPair = recPairs[checkedRec] # current pair of checked recipient
      # if score of the curRecPair is worse (>) than score of checked contender
      if RecipientPrefs[checkedRec][curRecPair] > RecipientPrefs[checkedRec][c]:
        echo("💔 ", MNames[c], " prefers ", FNames[checkedRec], " over ", FNames[contPairs[c]])
        echo("💔 ", FNames[checkedRec], " prefers ", MNames[c], " over ", MNames[curRecPair])
        echo "✗ Unstable"
        return false # unstable
  echo "✓ Stable"
  result = true

when isMainModule:
  var (contPairs, recPairs) = pair()
  printCoupleNames(contPairs)
  echo "Current pair analysis:"
  discard checkPairStability(contPairs, recPairs)
  perturbPairs(contPairs, recPairs)
  printCoupleNames(contPairs)
  echo "Current pair analysis:"
  discard checkPairStability(contPairs, recPairs)
Output:
abe 💑 ivy
bob 💑 cath
col 💑 dee
dan 💑 fay
ed 💑 jan
fred 💑 bea
gav 💑 gay
hal 💑 eve
ian 💑 hope
jon 💑 abi
Current pair analysis:
✓ Stable
Swapping hal & abe partners
abe 💑 eve
bob 💑 cath
col 💑 dee
dan 💑 fay
ed 💑 jan
fred 💑 bea
gav 💑 gay
hal 💑 ivy
ian 💑 hope
jon 💑 abi
Current pair analysis:
💔 hal prefers eve over ivy
💔 eve prefers hal over abe
✗ Unstable

Objective-C[edit]

Works with: XCode 4.5.1

(The C# version is essentially the same as this.)

//--------------------------------------------------------------------
// Person class

@interface Person : NSObject {
    NSUInteger _candidateIndex;
}
@property (nonatomic, strong)   NSString*   name;
@property (nonatomic, strong)   NSArray*    prefs;
@property (nonatomic, weak)     Person*     fiance;
@end

@implementation Person
+ (instancetype)named:(NSString *)name {
    return [[self alloc] initWithName:name];
}
- (instancetype)initWithName:(NSString *)name {
    if ((self = [super init])) {
        _name = name;
        _prefs = nil;
        _fiance = nil;
        _candidateIndex = 0;
    }
    return self;
}
- (BOOL)prefers:(Person *)p {
    return [_prefs indexOfObject:p] < [_prefs indexOfObject:_fiance];
}
- (Person *)nextCandidateNotYetProposedTo {
    if (_candidateIndex >= _prefs.count) return nil;
    return _prefs[_candidateIndex++];
}
- (void)engageTo:(Person *)p {
    if (p.fiance) p.fiance.fiance = nil;
    p.fiance = self;
    if (self.fiance) self.fiance.fiance = nil;
    self.fiance = p;
}
- (NSString *)description {
    return _name;
}
@end

//--------------------------------------------------------------------

BOOL isStable(NSArray *men) {
    NSArray *women = ((Person *)men[0]).prefs;
    for (Person *guy in men) {
        for (Person *gal in women) {
            if ([guy prefers:gal] && [gal prefers:guy])
                return NO;
        }
    }
    return YES;
}

//--------------------------------------------------------------------

void doMarriage() {
    Person *abe  = [Person named:@"abe"];
    Person *bob  = [Person named:@"bob"];
    Person *col  = [Person named:@"col"];
    Person *dan  = [Person named:@"dan"];
    Person *ed   = [Person named:@"ed"];
    Person *fred = [Person named:@"fred"];
    Person *gav  = [Person named:@"gav"];
    Person *hal  = [Person named:@"hal"];
    Person *ian  = [Person named:@"ian"];
    Person *jon  = [Person named:@"jon"];
    Person *abi  = [Person named:@"abi"];
    Person *bea  = [Person named:@"bea"];
    Person *cath = [Person named:@"cath"];
    Person *dee  = [Person named:@"dee"];
    Person *eve  = [Person named:@"eve"];
    Person *fay  = [Person named:@"fay"];
    Person *gay  = [Person named:@"gay"];
    Person *hope = [Person named:@"hope"];
    Person *ivy  = [Person named:@"ivy"];
    Person *jan  = [Person named:@"jan"];
    
    abe.prefs  = @[ abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay ];
    bob.prefs  = @[ cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay ];
    col.prefs  = @[ hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan ];
    dan.prefs  = @[ ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi ];
    ed.prefs   = @[ jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay ];
    fred.prefs = @[ bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay ];
    gav.prefs  = @[ gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay ];
    hal.prefs  = @[ abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee ];
    ian.prefs  = @[ hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve ];
    jon.prefs  = @[ abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope ];
    abi.prefs  = @[ bob, fred, jon, gav, ian, abe, dan, ed, col, hal ];
    bea.prefs  = @[ bob, abe, col, fred, gav, dan, ian, ed, jon, hal ];
    cath.prefs = @[ fred, bob, ed, gav, hal, col, ian, abe, dan, jon ];
    dee.prefs  = @[ fred, jon, col, abe, ian, hal, gav, dan, bob, ed ];
    eve.prefs  = @[ jon, hal, fred, dan, abe, gav, col, ed, ian, bob ];
    fay.prefs  = @[ bob, abe, ed, ian, jon, dan, fred, gav, col, hal ];
    gay.prefs  = @[ jon, gav, hal, fred, bob, abe, col, ed, dan, ian ];
    hope.prefs = @[ gav, jon, bob, abe, ian, dan, hal, ed, col, fred ];
    ivy.prefs  = @[ ian, col, hal, gav, fred, bob, abe, ed, jon, dan ];
    jan.prefs  = @[ ed, hal, gav, abe, bob, jon, col, ian, fred, dan ];
    
    NSArray *men = abi.prefs;
    
    NSUInteger freeMenCount = men.count;
    while (freeMenCount > 0) {
        for (Person *guy in men) {
            if (guy.fiance == nil) {
                Person *gal = [guy nextCandidateNotYetProposedTo];
                if (gal.fiance == nil) {
                    [guy engageTo:gal];
                    freeMenCount--;
                } else if ([gal prefers:guy]) {
                    [guy engageTo:gal];
                }
            }
        }
    }
    
    for (Person *guy in men) {
        printf("%s is engaged to %s\n", [guy.name UTF8String], [guy.fiance.name UTF8String]);
    }
    printf("Stable = %d\n", (int)isStable(men));

    printf("\nSwitching fred & jon's partners\n");
    [fred engageTo:abi];
    [jon engageTo:bea];
    printf("Stable = %d\n", (int)isStable(men));
}

//--------------------------------------------------------------------

int main(int argc, const char * argv[])
{
    @autoreleasepool {
        doMarriage();
    }
    return 0;
}
Output:
bob is engaged to cath
fred is engaged to bea
jon is engaged to abi
gav is engaged to gay
ian is engaged to hope
abe is engaged to ivy
dan is engaged to fay
ed is engaged to jan
col is engaged to dee
hal is engaged to eve
Stable = 1

Switching fred & jon's partners
Stable = 0

OCaml[edit]

let men = [
  "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"];
]

let women = [
  "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"];
]

type woman_name = string
type man_name = string

type man =
  { m_name: man_name;
    mutable free: bool;
    women_rank: woman_name list;
    has_proposed: (woman_name, unit) Hashtbl.t (* a set *)
  }

type woman =
  { w_name: woman_name;
    men_rank: man_name list;
    mutable engaged: man_name option
  }


let prefers w m1 m2 =
  (* returns true if w has a lower (better) rank for m1 than m2 *)
  let rec aux = function
  | [] -> invalid_arg "rank_cmp"
  | x::_ when x = m1 -> true
  | x::_ when x = m2 -> false
  | _::xs -> aux xs
  in
  aux w.men_rank

let take_while f lst =
  let rec aux acc = function
  | x::xs when f x -> aux (x::acc) xs
  | _ -> List.rev acc
  in
  aux [] lst

let more_ranked_than name =
  take_while ((<>) name)

let build_structs ~men ~women =
  List.map (fun (name, rank) ->
    { m_name = name;
      women_rank = rank;
      free = true;
      has_proposed = Hashtbl.create 42 }
  ) men,
  List.map (fun (name, rank) ->
    { w_name = name;
      men_rank = rank;
      engaged = None }
  ) women


let _stable_matching ms ws =
  let men_by_name = Hashtbl.create 42 in
  List.iter (fun m -> Hashtbl.add men_by_name m.m_name m) ms;
  let women_by_name = Hashtbl.create 42 in
  List.iter (fun w -> Hashtbl.add women_by_name w.w_name w) ws;
  try
    while true