Stable marriage problem: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|J}}) |
m (→{{header|Wren}}: Minor tidy) |
||
(39 intermediate revisions by 23 users not shown) | |||
Line 52:
# [http://www.ams.org/samplings/feature-column/fc-2015-03 The Stable Marriage Problem and School Choice]. (Excellent exposition)
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">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’)</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|AutoHotkey}}==
{{works with|AutoHotkey L}}
<
abe := ["abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"]
bob := ["cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"]
Line 143 ⟶ 272:
Else
Return "`nThese couples are stable.`n"
}</
{{out}}
<pre>Engagements:
Line 199 ⟶ 328:
=={{header|Batch File}}==
<syntaxhighlight lang="dos">:: Stable Marriage Problem in Rosetta Code
:: Batch File Implementation
@echo off
setlocal enabledelayedexpansion
set "male=
set "
set "abe[]=abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay"
set "
set "
set "
set "
set "
set "
set "
set "
set "
set "abi[]=bob, fred, jon, gav, ian, abe, dan, ed, col, hal"
set "
set "
set "
set "
set "
set "
set "
set "
set "
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
call :display
echo
call :isStable
echo
echo
call :swapper ed hal
echo
echo
call :display
echo
call :isStable
pause>nul
exit /b 0
:stableMatching
set "free_fem=%femm%"
for %%M in (%male%) do set "%%M_tried=0"
:match_loop
if "%free_men%"=="" goto :EOF
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}!"
set "m=%%m"
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 (
goto :EOF
:isStable
for %%
for %%g in (%male%) do (
set "girl_aboy=!%%f[%%g]!"
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
goto :EOF
:swapper
{{Out}}
<pre>HISTORY:
NEWLYWEDS:
gay
STABILITY = TRUE.
Line 374 ⟶ 512:
NEW-NEWLYWEDS:
eve
gay
STABILITY = FALSE.
eve and
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
DIM mname$(N), wname$(N), mpref$(N), wpref$(N), mpartner%(N), wpartner%(N)
DIM proposed&(N,N)
Line 457 ⟶ 595:
NEXT o%
NEXT m%
= TRUE</
'''Output:'''
<pre>
Line 479 ⟶ 617:
=={{header|Bracmat}}==
<
(bob.cath hope abi dee eve fay bea jan ivy gay)
(col.hope eve abi dee bea fay ivy gay cath jan)
Line 544 ⟶ 682:
| out$stable
)
);</
{{out}}
<pre>stable
Line 562 ⟶ 700:
=={{header|C}}==
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.
<
int verbose = 0;
Line 695 ⟶ 833:
return 0;
}</
{{out}}
<pre>Pairing:
Line 718 ⟶ 856:
Fred (w/ Cath) and Abi (w/ Jon) prefer each other over current pairing.
Marriages not stable</pre>
=={{header|C sharp|C#}}==
(This is a straight-up translation of the Objective-C version.)
<syntaxhighlight lang="csharp">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();
}
}
}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|C++}}==
<
#include <iostream>
#include <map>
Line 860 ⟶ 1,142:
check_stability(engaged, men_pref, women_pref);
}</
{{out}}
<pre>
Line 899 ⟶ 1,181:
</pre>
=={{header|
<syntaxhighlight lang="ceylon">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)
then true
else if (exists p2 = preferences.firstIndexWhere(f.equals))
}
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]) {
}
}
}
}
}
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!");
}</syntaxhighlight>
{{out}}
<pre>
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!</pre>
=={{header|CoffeeScript}}==
<
constructor: (@name, @preferences) ->
@mate = null
Line 1,171 ⟶ 1,487:
perturb guys
report_on_mates guys
report_potential_adulteries guys</
{{out}}
<pre>
Line 1,227 ⟶ 1,543:
=={{header|ColdFusion}}==
<
PERSON.CFC
Line 1,349 ⟶ 1,665:
}
}
</syntaxhighlight>
<
INDEX.CFM
Line 1,464 ⟶ 1,780:
}
</cfscript>
</syntaxhighlight>
{{out}}
<pre>
Line 1,531 ⟶ 1,847:
Nope, now everything is broken. Sharing spouses doesn't work, kids.
</pre>
=={{header|D}}==
From the Python and Java versions:
<
Line 1,662 ⟶ 1,979:
c = check!(true)(engagedTo, guyPrefers, galPrefers);
writeln("Marriages are ", c ? "stable" : "unstable");
}</
{{out}}
<pre>Engagements:
Line 1,688 ⟶ 2,005:
Marriages are unstable</pre>
===Stronger Version===
<
enum F { abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan }
Line 1,807 ⟶ 2,124:
checkStability(engaged, menPref, womenPref);
}
</syntaxhighlight>
{{out}}
<pre>Matchmaking:
Line 1,845 ⟶ 2,162:
=={{header|EchoLisp}}==
<
(lib 'hash)
;; input data
Line 1,920 ⟶ 2,237:
(error 'not-stable (list man woman)))))
</syntaxhighlight>
{{out}}
<pre>
Line 1,957 ⟶ 2,274:
=={{header|F_Sharp|F#}}==
<
Map.ofList
["abe", ["abi";"eve";"cath";"ivy";"jan";"dee";"fay";"bea";"hope";"gay"];
Line 2,103 ⟶ 2,420:
husbandOf = solution.husbandOf.Add( gal0, guy1 ).Add( gal1, guy0 ) }
printfn "Perturbed is stable: %A" (isStable perturbed)</
{{out}}
<pre>
Line 2,121 ⟶ 2,438:
=={{header|Go}}==
<
import "fmt"
Line 2,324 ⟶ 2,641:
fmt.Println("stable.")
return true
}</
{{out}}
<pre>
Line 2,378 ⟶ 2,695:
"Stable Matching" Solution:
<
import static Woman.*
Line 2,403 ⟶ 2,720:
}
engagedTo
}</
"Stability Checking" Solution:
(Could do more to eliminate common code. Maybe later.)
<
matches.collect{ girl, guy ->
int guysRank = galsGuyRanking[girl][guy]
Line 2,432 ⟶ 2,749:
true
}.every()
}</
Test (Stable and Perturbed):
<
abe, bob, col, dan, ed, fred, gav, hal, ian, jon
}
Line 2,490 ⟶ 2,807:
println ''
assert ! isStable(matches, mansWomanRanking, womansManRanking)</
{{out}}
<pre>abi (his '10' girl) is engaged to jon (her '8' guy)
Line 2,528 ⟶ 2,845:
=={{header|Haskell}}==
=== The solution ===
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.
<syntaxhighlight lang="haskell">{-# 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</syntaxhighlight>
Lenses allow us to get access to each person in the state, and even to the associated preference list:
<syntaxhighlight lang="haskell">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</syntaxhighlight>
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:
<syntaxhighlight lang="haskell">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 ]</syntaxhighlight>
This solution works not only for strings, but for any equable data.
=== The task ===
Here are the given preferences:
<syntaxhighlight lang="haskell">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"])]</syntaxhighlight>
The initial state:
<syntaxhighlight lang="haskell">s0 = State (fst <$> guys0) guys0 ((_2 %~ reverse) <$> girls0)</syntaxhighlight>
And the solution:
<pre>λ> 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
[]</pre>
Lets' make some perturbations: swap fiancees of abe and bob:
<pre>λ> 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"))</pre>
=={{header|Icon}} and {{header|Unicon}}==
<
procedure main()
Line 2,777 ⟶ 3,091:
return X
end</
{{libheader|Icon Programming Library}}
Line 2,829 ⟶ 3,143:
=={{header|J}}==
<
abe: abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay
bob: cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay
Line 2,900 ⟶ 3,214:
end.
assert-.bad
)</
For most of this, males and females are both represented by indices. Rows of <code>Mprefs</code> are indexed by a male index and each contains a list female indices, in priority order. Rows of <code>Fprefs</code> are indexed by a female index and each contains a list male indices in priority order. These indices select the corresponding names from <code>GuyNames</code> and <code>GalNames</code>.
Line 2,908 ⟶ 3,222:
Example use:
<
┌───┬────┬───┬───┬───┬────┬───┬───┬────┬───┐
│abe│bob │col│dan│ed │fred│gav│hal│ian │jon│
├───┼────┼───┼───┼───┼────┼───┼───┼────┼───┤
│ivy│cath│dee│fay│jan│bea │gay│eve│hope│abi│
└───┴────┴───┴───┴───┴────┴───┴───┴────┴───┘</
Stability check:
<
</
(no news is good news)
Line 2,924 ⟶ 3,238:
An altered result, and a stability check on it (showing what would happen for a bogus result):
<
┌───┬────┬───┬───┬───┬────┬───┬───┬────┬───┐
│abe│bob │col│dan│ed │fred│gav│hal│ian │jon│
Line 2,942 ⟶ 3,256:
└────┴───┘
|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.
=={{header|Java}}==
This is not a direct translation of [[#Python|Python]], but it's fairly close (especially the stability check).
<
public class Stable {
Line 3,126 ⟶ 3,440:
return true;
}
}</
{{out}}
<pre>abi is engaged to jon
Line 3,144 ⟶ 3,458:
=={{header|JavaScript}}==
<
var candidateIndex = 0;
Line 3,265 ⟶ 3,579:
doMarriage();
</syntaxhighlight>
{{out}}
Line 3,282 ⟶ 3,596:
Stable = No</pre>
=={{header|
'''Adapted from [[#Wren|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): .;`
<syntaxhighlight lang=jq>
# 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)
| $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
</syntaxhighlight>
{{output}}
'''Invocation:''' jq -nr -f stable-marriage-problem.jq
<pre>
["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.
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">
# 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
mfree[m]
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)
</syntaxhighlight>
{{out}}
<pre>
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---
</pre>
=={{header|Kotlin}}==
<syntaxhighlight lang="java">
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
}
}
else -> preferences.indexOf(p) < preferences.indexOf(matchedTo!!)
}
fun
}
fun match(males: Collection<Person>) {
while (males.find { it.matchedTo == null }?.also { match(it) } != null) {
}
}
while (male.matchedTo == null) {
male.preferences.removeAt(0).trySwap(male)
}
}
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) }
println("#### Unstable pair:
}
return stable
}
fun main(args: Array<String>) {
val inMales = mapOf(
"
"
"
"
"
"
"
"
"
"jon" to mutableListOf("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"))
val inFemales = mapOf(
"
"
"
"
"
"
"
"
"
"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)}")
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Lua}}==
{{trans|C#}}
<
Person.__index = Person
Line 3,539 ⟶ 4,325:
jon.fiance, fred.fiance = fred.fiance, jon.fiance
print('Stable: ', isStable(men))
</syntaxhighlight>
{{out}}
Line 3,561 ⟶ 4,347:
Stable: false
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica"><<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]</syntaxhighlight>
{{out}}
<pre>{{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</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">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)
</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Objective-C}}==
{{Works with|XCode 4.5.1}}
(The C# version is essentially the same as this.)
<
// Person class
Line 3,701 ⟶ 4,694:
}
return 0;
}</
{{out}}
Line 3,720 ⟶ 4,713:
=={{header|OCaml}}==
<
"abe", ["abi";"eve";"cath";"ivy";"jan";"dee";"fay";"bea";"hope";"gay"];
"bob", ["cath";"hope";"abi";"dee";"eve";"fay";"bea";"jan";"ivy";"gay"];
Line 3,877 ⟶ 4,870:
let engagements = perturb_engagements engagements in
print engagements;
;;</
{{out}}
<pre> fay is engaged with dan
Line 3,904 ⟶ 4,897:
=={{header|Perl}}==
<
use strict;
use warnings;
Line 4,020 ⟶ 5,013:
sub men { keys %{ $Likes{M} } }
sub women { keys %{ $Likes{W} } }</
{{out}}
<pre>
Line 4,048 ⟶ 5,041:
bea prefers fred to jon and fred prefers bea to abi
</pre>
=={{header|Phix}}==
{{trans|AutoHotkey}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">constant</span> <span style="color: #000000;">men</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"abe"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"bob"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"col"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"dan"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ed"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"fred"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"gav"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"hal"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ian"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"jon"</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">abe</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">bob</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">fred</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">jon</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">hen</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"abi"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"bea"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"cath"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"dee"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"eve"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"fay"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"gay"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"hope"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ivy"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"jan"</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">abi</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">hope</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span> <span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span>
<span style="color: #000080;font-style:italic;">-- Given a complete list of ranked preferences, where the most liked is to the left: </span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mpref</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">men</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">abe</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">abi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hope</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bob</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hope</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">col</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">hope</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dan</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hope</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abi</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ed</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">jan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hope</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fred</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hope</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gav</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">gay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hope</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">hal</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">abi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hope</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ian</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">hope</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">jon</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">abi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gay</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">eve</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bea</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dee</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cath</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ivy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hope</span><span style="color: #0000FF;">}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">hpref</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">abi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">bob</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fred</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jon</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bea</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">bob</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fred</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jon</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cath</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">fred</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bob</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jon</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dee</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">fred</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jon</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bob</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">eve</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">jon</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fred</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bob</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fay</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">bob</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jon</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fred</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">gay</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">jon</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fred</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bob</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">hope</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jon</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bob</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fred</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ivy</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ian</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fred</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bob</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jon</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">jan</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hal</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">gav</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">abe</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bob</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">jon</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ian</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fred</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dan</span><span style="color: #0000FF;">}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">engagements</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">freemen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">men</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Engagements:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- use the Gale Shapley algorithm to find a stable set of engagements:</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freemen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">man</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">freemen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">freemen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">freemen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">fem</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dumpee</span>
<span style="color: #000080;font-style:italic;">-- each male loops through all females in order of his preference until one accepts him</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">man</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">fem</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">man</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">dumpee</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">engagements</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dumpee</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span>
<span style="color: #008080;">or</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">man</span><span style="color: #0000FF;">,</span><span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">])<</span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dumpee</span><span style="color: #0000FF;">,</span><span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dumpee</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- if she was previously engaged</span>
<span style="color: #000000;">freemen</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">dumpee</span> <span style="color: #000080;font-style:italic;">-- he goes to the bottom of the list</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s dumped %s and accepted %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">],</span><span style="color: #000000;">men</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dumpee</span><span style="color: #0000FF;">],</span><span style="color: #000000;">men</span><span style="color: #0000FF;">[</span><span style="color: #000000;">man</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s accepted %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">],</span><span style="color: #000000;">men</span><span style="color: #0000FF;">[</span><span style="color: #000000;">man</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">engagements</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">man</span> <span style="color: #000080;font-style:italic;">-- the new engagement is registered</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nCouples:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">fem</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s is engaged to %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">],</span><span style="color: #000000;">men</span><span style="color: #0000FF;">[</span><span style="color: #000000;">engagements</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">]]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">stable</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">unstable</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">fem</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">man</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">engagements</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">man</span><span style="color: #0000FF;">])></span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">man</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">and</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">engagements</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])></span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">man</span><span style="color: #0000FF;">,</span><span style="color: #000000;">hpref</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">unstable</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nThese couples are not stable.\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">unstable</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s is engaged to %s but would prefer %s and %s is engaged to %s but would prefer %s\n"</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">men</span><span style="color: #0000FF;">[</span><span style="color: #000000;">man</span><span style="color: #0000FF;">],</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">fem</span><span style="color: #0000FF;">],</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">hen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">men</span><span style="color: #0000FF;">[</span><span style="color: #000000;">engagements</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]],</span><span style="color: #000000;">men</span><span style="color: #0000FF;">[</span><span style="color: #000000;">man</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">unstable</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nThese couples are stable.\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">stable</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nWhat if cath and ivy swap?\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">engagements</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cath</span><span style="color: #0000FF;">]:=</span><span style="color: #000000;">abe</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">engagements</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ivy</span><span style="color: #0000FF;">]:=</span><span style="color: #000000;">bob</span>
<span style="color: #000000;">stable</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{Out}}
<pre>
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 and accepted ian
abi dumped abe and accepted jon
dee accepted col
ivy dumped dan and 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?
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
</pre>
=={{header|PicoLisp}}==
<
*Boys (list
(de abe abi eve cath ivy jan dee fay bea hope gay)
Line 4,231 ⟶ 5,239:
(con (asoq 'fred *Couples) 'abi)
(con (asoq 'jon *Couples) 'bea)
(checkCouples)</
{{out}}
<pre>dee is engaged to col
Line 4,250 ⟶ 5,258:
gay likes jon better than gav and jon likes gay better than bea
bea likes fred better than jon and fred likes bea better than abi</pre>
=={{header|PowerShell}}==
<syntaxhighlight lang="PowerShell">
using namespace System.Collections.Generic
$ErrorActionPreference = 'Stop'
class Person{
#private
hidden [int] $_candidateIndex;
[string] $Name
#[System.Collections.Generic.List[Person]] $Prefs
[List[Person]] $Prefs
[Person] $Fiance
Person([string] $name) {
$this.Name = $name;
$this.Prefs = $null;
$this.Fiance = $null;
$this._candidateIndex = 0;
}
[bool] Prefers([Person] $p) {
return $this.Prefs.FindIndex({ param($o) $o -eq $p }) -lt $this.Prefs.FindIndex({ param($o) $o -eq $this.Fiance });
}
[Person] NextCandidateNotYetProposedTo() {
if ($this._candidateIndex -ge $this.Prefs.Count) {return $null;}
return $this.Prefs[$this._candidateIndex++];
}
[void] EngageTo([Person] $p) {
if ($p.Fiance -ne $null) {$p.Fiance.Fiance = $null};
$p.Fiance = $this;
if ($this.Fiance -ne $null){$this.Fiance.Fiance = $null};
$this.Fiance = $p;
}
}
class MainClass
{
static [bool] IsStable([List[Person]] $men) {
[List[Person]] $women = $men[0].Prefs;
foreach ($guy in $men){
foreach ($gal in $women) {
if ($guy.Prefers($gal) -and $gal.Prefers($guy))
{return $false};
}
}
return $true;
}
static [void] DoMarriage() {
[Person] $abe = [Person]::new("abe");
[Person] $bob = [Person]::new("bob");
[Person] $col = [Person]::new("col");
[Person] $dan = [Person]::new("dan");
[Person] $ed = [Person]::new("ed");
[Person] $fred = [Person]::new("fred");
[Person] $gav = [Person]::new("gav");
[Person] $hal = [Person]::new("hal");
[Person] $ian = [Person]::new("ian");
[Person] $jon = [Person]::new("jon");
[Person] $abi = [Person]::new("abi");
[Person] $bea = [Person]::new("bea");
[Person] $cath = [Person]::new("cath");
[Person] $dee = [Person]::new("dee");
[Person] $eve = [Person]::new("eve");
[Person] $fay = [Person]::new("fay");
[Person] $gay = [Person]::new("gay");
[Person] $hope = [Person]::new("hope");
[Person] $ivy = [Person]::new("ivy");
[Person] $jan = [Person]::new("jan");
$abe.Prefs =[Person[]]@($abi, $eve, $cath, $ivy, $jan, $dee, $fay, $bea, $hope, $gay)
$bob.Prefs = [Person[]] @($cath, $hope, $abi, $dee, $eve, $fay, $bea, $jan, $ivy, $gay);
$col.Prefs = [Person[]] @($hope, $eve, $abi, $dee, $bea, $fay, $ivy, $gay, $cath, $jan);
$dan.Prefs = [Person[]] @($ivy, $fay, $dee, $gay, $hope, $eve, $jan, $bea, $cath, $abi);
$ed.Prefs = [Person[]] @($jan, $dee, $bea, $cath, $fay, $eve, $abi, $ivy, $hope, $gay);
$fred.Prefs = [Person[]] @($bea, $abi, $dee, $gay, $eve, $ivy, $cath, $jan, $hope, $fay);
$gav.Prefs = [Person[]] @($gay, $eve, $ivy, $bea, $cath, $abi, $dee, $hope, $jan, $fay);
$hal.Prefs = [Person[]] @($abi, $eve, $hope, $fay, $ivy, $cath, $jan, $bea, $gay, $dee);
$ian.Prefs = [Person[]] @($hope, $cath, $dee, $gay, $bea, $abi, $fay, $ivy, $jan, $eve);
$jon.Prefs = [Person[]] @($abi, $fay, $jan, $gay, $eve, $bea, $dee, $cath, $ivy, $hope);
$abi.Prefs = [Person[]] @($bob, $fred, $jon, $gav, $ian, $abe, $dan, $ed, $col, $hal);
$bea.Prefs = [Person[]] @($bob, $abe, $col, $fred, $gav, $dan, $ian, $ed, $jon, $hal);
$cath.Prefs = [Person[]] @($fred, $bob, $ed, $gav, $hal, $col, $ian, $abe, $dan, $jon);
$dee.Prefs = [Person[]] @($fred, $jon, $col, $abe, $ian, $hal, $gav, $dan, $bob, $ed);
$eve.Prefs = [Person[]] @($jon, $hal, $fred, $dan, $abe, $gav, $col, $ed, $ian, $bob);
$fay.Prefs = [Person[]] @($bob, $abe, $ed, $ian, $jon, $dan, $fred, $gav, $col, $hal);
$gay.Prefs = [Person[]] @($jon, $gav, $hal, $fred, $bob, $abe, $col, $ed, $dan, $ian);
$hope.Prefs = [Person[]] @($gav, $jon, $bob, $abe, $ian, $dan, $hal, $ed, $col, $fred);
$ivy.Prefs = [Person[]] @($ian, $col, $hal, $gav, $fred, $bob, $abe, $ed, $jon, $dan);
$jan.Prefs = [Person[]] @($ed, $hal, $gav, $abe, $bob, $jon, $col, $ian, $fred, $dan);
[List[Person]] $men = [List[Person]]::new($abi.Prefs);
[int] $freeMenCount = $men.Count;
while ($freeMenCount -gt 0) {
foreach ($guy in $men) {
if ($guy.Fiance -eq $null) {
[Person]$gal = $guy.NextCandidateNotYetProposedTo();
if ($gal.Fiance -eq $null) {
$guy.EngageTo($gal);
$freeMenCount--;
}
else{
if ($gal.Prefers($guy)) {
$guy.EngageTo($gal);
}
}
}
}
}
foreach ($guy in $men) {
write-host $guy.Name " is engaged to " $guy.Fiance.Name
}
write-host "Stable = " ([MainClass]::IsStable($men))
write-host "Switching fred & jon's partners";
[Person] $jonsFiance = $jon.Fiance;
[Person] $fredsFiance = $fred.Fiance;
$fred.EngageTo($jonsFiance);
$jon.EngageTo($fredsFiance);
write-host "Stable = " ([MainClass]::IsStable($men));
}
static [void] Main([string[]] $args)
{
[MainClass]::DoMarriage();
}
}
[MainClass]::DoMarriage()
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Prolog}}==
{{Works with|SWI-Prolog}}{{libheader|XPCE}}
XPCE is used for its integrated messaging system.
<
% facts
prefere(abe,[ abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay]).
Line 4,527 ⟶ 5,695:
( (IY12 < IY11 , IX21 < IX22);
(IY21 < IY22 , IX12 < IX11)).
</syntaxhighlight>
{{out}}
<pre> ?- stable_mariage.
Line 4,554 ⟶ 5,722:
true </pre>
A more Prolog-ish version (working with SWI-Prolog) could be :
<
% person(Name, Preference, Status, Candidate)
% prop(Name, List_of_Candidates) (for a woman)
Line 4,767 ⟶ 5,935:
% A couple is unstable
( (IY12 < IY11 , IX21 < IX22);
(IY21 < IY22 , IX12 < IX11)).</
=={{header|PureBasic}}==
This approach uses a messaging system to pass messages between prospective partners.
<
DataSection
Line 4,944 ⟶ 6,112:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf</
{{out}}
<pre>Marriages:
Line 4,972 ⟶ 6,140:
=={{header|Python}}==
<
guyprefers = {
Line 5,074 ⟶ 6,242:
print()
print('Engagement stability check PASSED'
if check(engaged) else 'Engagement stability check FAILED')</
{{out}}
<pre>Engagements:
Line 5,112 ⟶ 6,280:
fay and jon like each other better than their present partners: dan and bea, respectively
Engagement stability check FAILED</pre>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
Line 5,405 ⟶ 6,368:
(swap! (hash-ref matches (car M)) (hash-ref matches (cadr M))))
(check-stability)
</syntaxhighlight>
Sample run:
Line 5,425 ⟶ 6,388:
</pre>
=={{header|
(formerly Perl 6)
{{Works with|rakudo|2016.10}}
{{trans|Perl}}
<syntaxhighlight lang="raku" line>my %he-likes =
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 >,
;
my %she-likes =
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 >,
;
my %fiancé;
my %fiancée;
my %proposed;
sub she-prefers ($her, $hottie) { .index($hottie) < .index(%fiancé{$her}) given ~%she-likes{$her} }
sub he-prefers ($him, $hottie) { .index($hottie) < .index(%fiancée{$him}) given ~%he-likes{$him} }
match'em;
check-stability;
perturb'em;
check-stability;
sub match'em { #'
say 'Matchmaking:';
while unmatched-guy() -> $guy {
my $gal = preferred-choice($guy);
%proposed{"$guy $gal"} = '❤';
if not %fiancé{$gal} {
engage($guy, $gal);
say "\t$gal and $guy";
}
elsif she-prefers($gal, $guy) {
my $engaged-guy = %fiancé{$gal};
engage($guy, $gal);
%fiancée{$engaged-guy} = '';
say "\t$gal dumped $engaged-guy for $guy";
}
}
}
sub check-stability {
my @instabilities = gather for flat %he-likes.keys X %she-likes.keys -> $m, $w {
if he-prefers($m, $w) and she-prefers($w, $m) {
take "\t$w prefers $m to %fiancé{$w} and $m prefers $w to %fiancée{$m}";
}
}
say 'Stablility:';
if @instabilities {
.say for @instabilities;
}
else {
say "\t(all marriages stable)";
}
}
sub unmatched-guy { %he-likes.keys.first: { not %fiancée{$_} } }
sub preferred-choice($guy) { %he-likes{$guy}.first: { not %proposed{"$guy $_" } } }
sub engage($guy, $gal) {
%fiancé{$gal} = $guy;
%fiancée{$guy} = $gal;
}
sub perturb'em { #'
say 'Perturb:';
say "\tengage abi with fred and bea with jon";
engage('fred', 'abi');
engage('jon', 'bea');
}</syntaxhighlight>
{{out}}
<pre>Matchmaking:
cath and bob
ivy and dan
abi and jon
hope and ian
jan and ed
eve and abe
eve dumped abe for hal
ivy dumped dan for abe
fay and dan
gay and gav
bea and fred
dee and col
Stablility:
(all marriages stable)
Perturb:
engage abi with fred and bea with jon
Stablility:
fay prefers jon to dan and jon prefers fay to bea
eve prefers jon to hal and jon prefers eve to bea
gay prefers jon to gav and jon prefers gay to bea
bea prefers fred to jon and fred prefers bea to abi</pre>
=={{header|REXX}}==
Algorithm used: see link https://www.youtube.com/watch?v=Qcv1IqHWAzg
<
* pref.b Preferences of boy b
* pref.g Preferences of girl g
Line 5,626 ⟶ 6,702:
If debug Then
Call dbg arg(1)
Return
repl: Procedure
Parse Arg s,new,old
Do i=1 To 100 Until p=0
p=pos(old,s)
If p>0 Then
s=left(s,p-1)||new||substr(s,p+length(old))
End
Return s </syntaxhighlight>
{{out}}
<pre>
Line 5,651 ⟶ 6,735:
DAN matches FAY</pre>
=={{header|
<syntaxhighlight lang="ruby">class Person
def initialize(name)
@name = name
@fiance = nil
@preferences = []
@proposals = []
end
attr_reader :name, :proposals
attr_accessor :fiance, :preferences
def to_s
end
def free
@fiance = nil
end
def single?
@fiance == nil
end
def engage(person)
self.fiance = person
person.fiance = self
end
def better_choice?(person)
@preferences.index(person) < @preferences.index(@fiance)
end
def propose_to(person)
puts "#{self} proposes to #{person}" if $DEBUG
@proposals << person
person.respond_to_proposal_from(self)
end
def respond_to_proposal_from(person)
if single?
puts "#{self} accepts proposal from #{person}" if $DEBUG
engage(person)
elsif better_choice?(person)
puts "#{self} dumps #{@fiance} for #{person}" if $DEBUG
@fiance.free
engage(person)
else
puts "#{self} rejects proposal from #{person}" if $DEBUG
end
end
########################################################################
# initialize data
prefs = {
'abe' => %w[abi eve cath ivy jan dee fay bea hope gay],
'bob' => %w[cath hope abi dee eve fay bea jan ivy gay],
'col' => %w[hope eve abi dee bea fay ivy gay cath jan],
'dan' => %w[ivy fay dee gay hope eve jan bea cath abi],
'ed' => %w[jan dee bea cath fay eve abi ivy hope gay],
'fred' => %w[bea abi dee gay eve ivy cath jan hope fay],
'gav' => %w[gay eve ivy bea cath abi dee hope jan fay],
'hal' => %w[abi eve hope fay ivy cath jan bea gay dee],
'ian' => %w[hope cath dee gay bea abi fay ivy jan eve],
'jon' => %w[abi fay jan gay eve bea dee
'abi' => %w[bob fred jon gav ian abe dan ed col hal],
'bea' => %w[bob abe col fred gav dan ian ed jon hal],
'cath' => %w[fred bob ed gav hal col ian abe dan jon],
'dee' => %w[fred jon col abe ian hal gav dan bob ed],
'eve' => %w[jon hal fred dan abe gav col ed ian bob],
'fay' => %w[bob abe ed ian jon dan fred gav col hal],
'gay' => %w[jon gav hal fred bob abe col ed dan ian],
'hope' => %w[gav jon bob abe ian dan hal ed col
'ivy' => %w[ian col hal gav fred bob abe
'jan' => %w[ed hal gav abe bob jon col ian fred dan],
}
@men = Hash[
%w[abe bob col dan ed fred gav hal ian jon].collect do |name|
[name, Person.new(name)]
end
]
@women = Hash[
%w[abi bea cath dee eve fay gay hope ivy jan].collect do |name|
[name, Person.new(name)]
end
]
@men.each {|name, man| man.preferences = @women.values_at(*prefs[name])}
@women.each {|name, woman| woman.preferences = @men.values_at(*prefs[name])}
########################################################################
# perform the matching
def match_couples(men, women)
men.each_value {|man| man.free}
women.each_value {|woman| woman.free}
while m = men.values.find {|man| man.single?} do
puts "considering single man #{m}" if $DEBUG
w = m.preferences.find {|woman| not m.proposals.include?(woman)}
m.propose_to(w)
end
end
match_couples @men, @women
@men.each_value.collect {|man| puts "#{man} + #{man.fiance}"}
########################################################################
# check for stability
class Person
def more_preferable_people
( @preferences.partition {|p| better_choice?(p)} ).first
end
end
require 'set'
def stability(men)
unstable = Set.new
men.each_value do |man|
woman = man.fiance
puts "considering #{man} and #{woman}" if $DEBUG
man.more_preferable_people.each do |other_woman|
if other_woman.more_preferable_people.include?(man)
puts "an unstable pairing: #{man} and #{other_woman}" if $DEBUG
unstable << [man, other_woman]
end
end
woman.more_preferable_people.each do |other_man|
if other_man.more_preferable_people.include?(woman)
puts "an unstable pairing: #{woman} and #{other_man}" if $DEBUG
unstable << [other_man, woman]
end
end
end
if unstable.empty?
puts "these couples are stable"
else
puts "uh oh"
unstable.each do |a,b|
puts "#{a} is engaged to #{a.fiance} but would prefer #{b}, and #{b} is engaged to #{b.fiance} but would prefer #{a}"
end
end
end
stability @men
########################################################################
# perturb
puts "\nwhat if abe and bob swap..."
def swap(m1, m2)
w1 = m1.fiance
w2 = m2.fiance
m1.fiance = w2
w1.fiance = m2
m2.fiance = w1
w2.fiance = m1
end
swap *@men.values_at('abe','bob')
@men.each_value.collect {|man| puts "#{man} + #{man.fiance}"}
stability @men</syntaxhighlight>
{{out}}
<pre>abe + ivy
bob + cath
col + dee
dan + fay
ed + jan
fred + bea
gav + gay
hal + eve
ian + hope
jon + abi
these couples are stable
what if abe and bob swap...
abe + cath
bob + ivy
col + dee
dan + fay
ed + jan
fred + bea
gav + gay
hal + eve
ian + hope
jon + abi
uh oh
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 hope, and hope is engaged to ian but would prefer bob
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 fay, and fay is engaged to dan but would prefer bob
bob is engaged to ivy but would prefer bea, and bea is engaged to fred but would prefer bob</pre>
Hmm, turns out Bob is a popular guy...
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="scala">object SMP extends App {
private def checkMarriages(): Unit =
if (check)
println("Marriages are stable")
else
println("Marriages are unstable")
private def swap() {
val girl1 = girls.head
val girl2 = girls(1)
val tmp = girl2 -> matches(girl1)
matches += girl1 -> matches(girl2)
matches += tmp
println(girl1 + " and " + girl2 + " have switched partners")
}
private type TM = scala.collection.mutable.TreeMap[String, String]
private def
if (!girls.toSet.subsetOf(matches.keySet) || !guys.toSet.subsetOf(matches.values.toSet))
return false
val invertedMatches = new
matches
for ((k, v) <- matches) {
val shePrefers = girlPrefers(k)
val sheLikesBetter =
val hePrefers = guyPrefers(v)
val
for (guy <- sheLikesBetter) {
val fiance = invertedMatches(guy)
val guy_p = guyPrefers(guy)
if (guy_p.indexOf(fiance) > guy_p.indexOf(k)) {
println(s"$k likes $guy better than $v and $guy likes $k better than their current partner")
return false
}
}
for (girl <- heLikesBetter) {
val fiance = matches(girl)
val girl_p = girlPrefers(girl)
if (girl_p.indexOf(fiance) > girl_p.indexOf(v)) {
println(s"$v likes $girl better than $k and $girl likes $v better than their current partner")
return false
}
}
}
}
private val guys = "abe" :: "bob" :: "col" :: "dan" :: "ed" :: "fred" :: "gav" :: "hal" :: "ian" :: "jon" :: Nil
private val girls = "abi" :: "bea" :: "cath" :: "dee" :: "eve" :: "fay" :: "gay" :: "hope" :: "ivy" :: "jan" :: Nil
private val guyPrefers =
"bob" -> List("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
"col" -> List("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
"dan" -> List("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"),
"ed" -> List("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"),
"fred" -> List("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"),
"gav" -> List("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"),
"hal" -> List("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"),
"ian" -> List("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
"jon" -> List("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"))
private val girlPrefers = Map("abi" -> List("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
"bea" -> List("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
"cath" -> List("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
"dee" -> List("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"),
"eve" -> List("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"),
"fay" -> List("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"),
"gay" -> List("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"),
"hope" -> List("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"),
"ivy" -> List("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
"jan" -> List("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"))
private lazy val matches = {
val engagements = new TM
val freeGuys = scala.collection.mutable.Queue.empty ++ guys
while (freeGuys.nonEmpty) {
val guy = freeGuys.dequeue()
val guy_p = guyPrefers(guy)
var break = false
for (girl <- guy_p)
if (!break)
if (!engagements.contains(girl)) {
engagements(girl) = guy
break = true
}
else {
val other_guy = engagements(girl)
val girl_p = girlPrefers(girl)
if (girl_p.indexOf(guy) < girl_p.indexOf(other_guy)) {
engagements(girl) = guy
freeGuys += other_guy
break = true
}
}
}
engagements foreach { e => println(s"${e._1} is engaged to ${e._2}") }
engagements
}
checkMarriages()
swap()
checkMarriages()
}</syntaxhighlight>
{{out}}
See Java output.
=={{header|Seed7}}==
<
const type: preferences is hash [string] array string;
Line 5,927 ⟶ 7,202:
writeln;
writeln("Marriages are " <& [] ("unstable", "stable") [succ(ord(check(engagedTo, guyPrefers, girlPrefers)))]);
end func;</
Output:
Line 5,968 ⟶ 7,243:
=={{header|Sidef}}==
{{trans|
<
abe => < abi eve cath ivy jan dee fay bea hope gay >,
bob => < cath hope abi dee eve fay bea jan ivy gay >,
Line 6,057 ⟶ 7,332:
perturb_em();
check_stability();</
{{out}}
<pre>
Line 6,089 ⟶ 7,364:
The data set package:
<
is
Line 6,132 ⟶ 7,407:
end Preferences;
</syntaxhighlight>
The package for creating the engagements and checking stability. This package can be analysed by the SPARK tools and proved to be free of any run-time error.
<
--# inherit Preferences;
package Propose
Line 6,153 ⟶ 7,428:
end Propose;
</syntaxhighlight>
<
use type Preferences.Extended_Rank;
use type Preferences.Girl;
Line 6,292 ⟶ 7,567:
end Propose;
</syntaxhighlight>
The test program tests all pairwise exchanges. This is Ada, it is not SPARK.
(Text IO is quite tedious in SPARK - it's not what the language was designed for.)
<
-- Test program.
--
Line 6,362 ⟶ 7,637:
end MatchMaker;
</syntaxhighlight>
The begining of the output from the test. All pairwise exchanges create unstable pairings.
<pre>ABI marries JON
Line 6,385 ⟶ 7,660:
Pairs are Unstable: JON and ABI prefer each other.
</pre>
=={{header|Swift}}==
{{trans|JavaScript}}
<
let name:String
var candidateIndex = 0
Line 6,524 ⟶ 7,800:
}
doMarriage()</
{{out}}
<pre>
Line 6,543 ⟶ 7,819:
=={{header|Tcl}}==
{{trans|Python}}
<
# Functions as aliases to standard commands
Line 6,658 ⟶ 7,934:
}
puts ""
puts "Engagement stability check [lindex {FAILED PASSED} [check $engaged]]"</
{{out}}
<pre>
Line 6,697 ⟶ 7,973:
fred and bea like each other better than their present partners, abi and jon respectively
Engagement stability check FAILED
</pre>
=={{header|UNIX Shell}}==
{{works with|Bourne Again Shell|4.0}}
{{trans|AutoHotkey}}
<syntaxhighlight lang="shell">#!/usr/bin/env bash
main() {
# Our ten males:
local males=(abe bob col dan ed fred gav hal ian jon)
# And ten females:
local females=(abi bea cath dee eve fay gay hope ivy jan)
# Everyone's preferences, ranked most to least desirable:
local abe=( abi eve cath ivy jan dee fay bea hope gay )
local abi=( bob fred jon gav ian abe dan ed col hal )
local bea=( bob abe col fred gav dan ian ed jon hal )
local bob=(cath hope abi dee eve fay bea jan ivy gay )
local cath=(fred bob ed gav hal col ian abe dan jon )
local col=(hope eve abi dee bea fay ivy gay cath jan )
local dan=( ivy fay dee gay hope eve jan bea cath abi )
local dee=(fred jon col abe ian hal gav dan bob ed )
local ed=( jan dee bea cath fay eve abi ivy hope gay )
local eve=( jon hal fred dan abe gav col ed ian bob )
local fay=( bob abe ed ian jon dan fred gav col hal )
local fred=( bea abi dee gay eve ivy cath jan hope fay )
local gav=( gay eve ivy bea cath abi dee hope jan fay )
local gay=( jon gav hal fred bob abe col ed dan ian )
local hal=( abi eve hope fay ivy cath jan bea gay dee )
local hope=( gav jon bob abe ian dan hal ed col fred)
local ian=(hope cath dee gay bea abi fay ivy jan eve )
local ivy=( ian col hal gav fred bob abe ed jon dan )
local jan=( ed hal gav abe bob jon col ian fred dan )
local jon=( abi fay jan gay eve bea dee cath ivy hope)
# A place to store the engagements:
local -A engagements=()
# Our list of free males, initially comprised of all of them:
local freemales=( "${males[@]}" )
# Now we use the Gale-Shapley algorithm to find a stable set of engagements
# Loop over the free males. Note that we can't use for..in because the body
# of the loop may modify the array we're looping over
local -i m=0
while (( m < ${#freemales[@]} )); do
local male=${freemales[m]}
let m+=1
# This guy's preferences
eval 'local his=("${'"$male"'[@]}")'
# Starting with his favorite
local -i f=0
local female=${his[f]}
# Find her preferences
eval 'local hers=("${'"$female"'[@]}")'
# And her current fiancé, if any
local fiance=${engagements[$female]}
# If she has a fiancé and prefers him to this guy, look for this guy's next
# best choice
while [[ -n $fiance ]] &&
(( $(index "$male" "${hers[@]}") > $(index "$fiance" "${hers[@]}") )); do
let f+=1
female=${his[f]}
eval 'hers=("${'"$female"'[@]}")'
fiance=${engagements[$female]}
done
# If we're still on someone who's engaged, it means she prefers this guy
# to her current fiancé. Dump him and put him at the end of the free list.
if [[ -n $fiance ]]; then
freemales+=("$fiance")
printf '%-4s rejected %-4s\n' "$female" "$fiance"
fi
# We found a match! Record it
engagements[$female]=$male
printf '%-4s accepted %-4s\n' "$female" "$male"
done
# Display the final result, which should be stable
print_couples engagements
# Verify its stability
print_stable engagements "${females[@]}"
# Try a swap
printf '\nWhat if cath and ivy swap partners?\n'
local temp=${engagements[cath]}
engagements[cath]=${engagements[ivy]}
engagements[ivy]=$temp
# Display the new result, which should be unstable
print_couples engagements
# Verify its instability
print_stable engagements "${females[@]}"
}
# utility function - get index of an item in an array
index() {
local needle=$1
shift
local haystack=("$@")
local -i i
for i in "${!haystack[@]}"; do
if [[ ${haystack[i]} == $needle ]]; then
printf '%d\n' "$i"
return 0
fi
done
return 1
}
# print the couples from the engagement array; takes name of array as argument
print_couples() {
printf '\nCouples:\n'
local keys
mapfile -t keys < <(eval 'printf '\''%s\n'\'' "${!'"$1"'[@]}"' | sort)
local female
for female in "${keys[@]}"; do
eval 'local male=${'"$1"'["'"$female"'"]}'
printf '%-4s is engaged to %-4s\n' "$female" "$male"
done
printf '\n'
}
# print whether a set of engagements is stable; takes name of engagement array
# followed by the list of females
print_stable() {
if stable "$@"; then
printf 'These couples are stable.\n'
else
printf 'These couples are not stable.\n'
fi
}
# determine if a set of engagements is stable; takes name of engagement array
# followed by the list of females
stable() {
local dict=$1
shift
eval 'local shes=("${!'"$dict"'[@]}")'
eval 'local hes=("${'"$dict"'[@]}")'
local -i i
local -i result=0
for (( i=0; i<${#shes[@]}; ++i )); do
local she=${shes[i]} he=${hes[i]}
eval 'local his=("${'"$he"'[@]}")'
local alt
for alt in "$@"; do
eval 'local fiance=${'"$dict"'["'"$alt"'"]}'
eval 'local hers=("${'"$alt"'[@]}")'
if (( $(index "$she" "${his[@]}") > $(index "$alt" "${his[@]}")
&& $(index "$fiance" "${hers[@]}") > $(index "$he" "${hers[@]}") ))
then
printf '%-4s is engaged to %-4s but prefers %4s, ' "$he" "$she" "$alt"
printf 'while %-4s is engaged to %-4s but prefers %4s.\n' "$alt" "$fiance" "$he"
result=1
fi
done
done
if (( result )); then printf '\n'; fi
return $result
}
main "$@"</syntaxhighlight>
{{Out}}
<pre>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 rejected col
hope accepted ian
abi rejected abe
abi accepted jon
dee accepted col
ivy rejected 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 partners?
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
bob is engaged to ivy but prefers abi, while abi is engaged to jon but prefers bob.
bob is engaged to ivy but prefers bea, while bea is engaged to fred but prefers bob.
bob is engaged to ivy but prefers cath, while cath is engaged to abe but prefers bob.
bob is engaged to ivy but prefers fay, while fay is engaged to dan but prefers bob.
bob is engaged to ivy but prefers hope, while hope is engaged to ian but prefers bob.
These couples are not stable.
</pre>
=={{header|Ursala}}==
<
{
Line 6,747 ⟶ 8,248:
'stable': match/men women,
'perturbed': ~&lSrSxPp match/men women,
'preferred': preferred/(men,women) ~&lSrSxPp match/men women></
The matches are perturbed by reversing the order of the women.
{{out}}
Line 6,801 ⟶ 8,302:
=={{header|VBA}}==
<pre>2 methods will be shown here:
1 - using basic VBA-features for strings
2 - using the scripting.dictionary library</pre>
'''The string approach'''<br/>
<syntaxhighlight lang="vb">Sub M_snb()
c00 = "_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 "
sn = Filter(Filter(Split(c00), "_"), "-", 0)
Do
c01 = Mid(c00, InStr(c00, sn(0) & " "))
st = Split(Left(c01, InStr(Mid(c01, 2), "_")))
For j = 1 To UBound(st) - 1
If InStr(c00, "_" & st(j) & " ") > 0 Then
c00 = Replace(Replace(c00, sn(0), sn(0) & "-" & st(j)), "_" & st(j), "_" & st(j) & "." & Mid(sn(0), 2))
Exit For
Else
c02 = Filter(Split(c00, "_"), st(j) & ".")(0)
c03 = Split(Split(c02)(0), ".")(1)
If InStr(c02, " " & Mid(sn(0), 2) & " ") < InStr(c02, " " & c03 & " ") Then
c00 = Replace(Replace(Replace(c00, c03 & "-" & st(j), c03), sn(0), sn(0) & "-" & st(j)), "_" & st(j), "_" & st(j) & "." & Mid(sn(0), 2))
Exit For
End If
End If
Next
sn = Filter(Filter(Filter(Split(c00), "_"), "-", 0), ".", 0)
Loop Until UBound(sn) = -1
MsgBox Replace(Join(Filter(Split(c00), "-"), vbLf), "_", "")
End Sub</syntaxhighlight>
'''The Dictionary approach'''
<syntaxhighlight lang="vb">Sub M_snb()
Set d_00 = CreateObject("scripting.dictionary")
Set d_01 = CreateObject("scripting.dictionary")
Set d_02 = CreateObject("scripting.dictionary")
sn = Split("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 ", "_")
sp = Split("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 ", "_")
For j = 0 To UBound(sn)
d_00(Split(sn(j))(0)) = ""
d_01(Split(sp(j))(0)) = ""
d_02(Split(sn(j))(0)) = sn(j)
d_02(Split(sp(j))(0)) = sp(j)
Next
Do
For Each it In d_00.keys
If d_00.Item(it) = "" Then
st = Split(d_02.Item(it))
For jj = 1 To UBound(st)
If d_01(st(jj)) = "" Then
d_00(st(0)) = st(0) & vbTab & st(jj)
d_01(st(jj)) = st(0)
Exit For
ElseIf InStr(d_02.Item(st(jj)), " " & st(0) & " ") < InStr(d_02.Item(st(jj)), " " & d_01(st(jj)) & " ") Then
d_00(d_01(st(jj))) = ""
d_00(st(0)) = st(0) & vbTab & st(jj)
d_01(st(jj)) = st(0)
Exit For
End If
Next
End If
Next
Loop Until UBound(Filter(d_00.items, vbTab)) = d_00.Count - 1
MsgBox Join(d_00.items, vbLf)
End Sub</syntaxhighlight>
{{out}}
<pre>
abe - ivy
bob - cath
col - dee
dan - fay
ed - jan
fred - bea
gav - gay
hal - eve
ian - hope
jan - abi
</pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-dynamic}}
Although this is a faithful translation, the results are not identical to those of Go as map iteration order in both languages is undefined.
<syntaxhighlight lang="wren">import "./dynamic" for Struct
var 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"]
}
var 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 implements the Gale/Shapely algorithm.
var pair = Fn.new { |pPref, rPref|
// code is destructive on the maps, so work with copies
var pFree = {}
for (me in pPref) pFree[me.key] = me.value
var rFree = {}
for (me in rPref) rFree[me.key] = me.value
// struct only used in this function.
// preferences must be saved in case engagement is broken.
var Save = Struct.create("Save", ["proposer", "pPref", "rPref"])
var 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
while (pFree.count > 0) { // while there is a free proposer,
var proposer
var ppref
for (me in pFree) {
proposer = me.key
ppref = me.value
break // pick a proposer at random, whatever map iteration delivers first.
}
if (ppref.count == 0) continue // if proposer has no possible recipients, skip
// WP: w = m's highest ranked such woman to whom he has not yet proposed
var recipient = ppref[0] // highest ranged is first in list.
ppref = ppref[1..-1] // pop from list
var rpref = {}
// WP: if w is free
if (rpref = rFree[recipient]) {
// WP: (m, w) become engaged
// (common code follows if statement)
} else {
// WP: else some pair (m', w) already exists
var s = proposals[recipient] // get proposal saved preferences
// WP: if w prefers m to m'
if (s.rPref[proposer] < s.rPref[s.proposer]) {
System.print("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
}
}
System.print("engagement: %(recipient) %(proposer)")
proposals[recipient] = Save.new(proposer, ppref, rpref)
pFree.remove(proposer)
rFree.remove(recipient)
}
// construct return value
var ps = {}
for (me in proposals) {
ps[me.key] = me.value.proposer
}
return ps
}
var validateStable = Fn.new { |ps, pPref, rPref|
for (me in ps) System.print("%(me.key) %(me.value)")
for (me in ps) {
var r = me.key
var p = me.value
for (rp in pPref[p]) {
if (rp == r) break
var rprefs = rPref[rp]
if (rprefs[p] < rprefs[ps[rp]]) {
System.print("unstable.")
System.print("%(p) and %(rp) would prefer each other over their current pairings.")
return false
}
}
}
System.print("stable.")
return true
}
// get parings by Gale/Shapley algorithm
var ps = pair.call(mPref, wPref)
// show results
System.print("\nresult:")
if (!validateStable.call(ps, mPref, wPref)) return
// perturb
while (true) {
var i = 0
var w2 = List.filled(2, null)
var m2 = List.filled(2, null)
for (me in ps) {
w2[i] = me.key
m2[i] = me.value
if (i == 1) break
i = i + 1
}
System.print("\nexchanging partners of %(m2[0]) and %(m2[1])")
ps[w2[0]] = m2[1]
ps[w2[1]] = m2[0]
// validate perturbed parings
if (!validateStable.call(ps, mPref, wPref)) return
// if those happened to be stable as well, perturb more
}</syntaxhighlight>
{{out}}
<pre>
engagement: hope col
engagement broken: hope col
engagement: hope ian
engagement: eve col
engagement: cath bob
engagement: ivy dan
engagement: bea fred
engagement: gay gav
engagement: abi hal
engagement: jan ed
engagement broken: abi hal
engagement: abi abe
engagement broken: eve col
engagement: eve hal
engagement: dee col
engagement broken: abi abe
engagement: abi jon
engagement broken: ivy dan
engagement: ivy abe
engagement: fay dan
result:
bea fred
gay gav
eve hal
dee col
hope ian
fay dan
abi jon
cath bob
ivy abe
jan ed
stable.
exchanging partners of fred and gav
bea gav
gay fred
eve hal
dee col
hope ian
fay dan
abi jon
cath bob
ivy abe
jan ed
unstable.
gav and gay would prefer each other over their current pairings.
</pre>
=={{header|XSLT 2.0}}==
Line 6,967 ⟶ 8,657:
Assume that the input is in XML form as listed [[Stable marriage problem/XSLT input|here]]. The following XSLT 2.0 style-sheet...
<syntaxhighlight lang="text"><xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:fn="http://www.w3.org/2005/xpath-functions"
Line 7,102 ⟶ 8,792:
</xsl:function>
</xsl:stylesheet></
...when applied to the said input document will yield...
<syntaxhighlight lang="text"><t>
<m:stable-marriage-problem-result xmlns:m="http://rosettacode.org/wiki/Stable_marriage_problem">
<m:solution is-stable="true">
Line 7,153 ⟶ 8,843:
<m:message>The perturbed configuration is unstable.</m:message>
</m:stable-marriage-problem-result>
</t></
=={{header|zkl}}==
{{trans|PicoLisp}}
<
Boys=
"abe", "abi eve cath ivy jan dee fay bea hope gay".split(),
"bob", "cath hope abi dee eve fay bea jan ivy gay".split(),
Line 7,169 ⟶ 8,859:
"ian", "hope cath dee gay bea abi fay ivy jan eve".split(),
"jon", "abi fay jan gay eve bea dee cath ivy hope".split(), ),
Girls=
"abi", "bob fred jon gav ian abe dan ed col hal".split(),
"bea", "bob abe col fred gav dan ian ed jon hal".split(),
Line 7,182 ⟶ 8,872:
Couples=List(); // ( (boy,girl),(boy,girl),...)
Boyz:=Boys.pump(
while( bgs:=Boyz.filter1( 'wrap([(Boy,gs)]){ // while unattached boy
gs and (not Couples.filter1("holds",Boy))
Line 7,218 ⟶ 8,908:
Couples.filter1("holds","fred")[1]="abi";
Couples.filter1("holds","jon") [1]="bea";
checkCouples(Couples);</
{{out}}
<pre>
|