Stable marriage problem
You are encouraged to solve this task according to the task description, using any language you may know.
Solve the Stable marriage problem using the Gale/Shapley algorithm.
Problem description
Given an equal number of men and women to be paired for marriage, each man ranks all the women in order of his preference and each women ranks all the men in order of her preference.
A stable set of engagements for marriage is one where no man prefers a women over the one he is engaged to, where that other woman also prefers that man over the one she is engaged to. I.e. with consulting marriages, there would be no reason for the engagements between the people to change.
Gale and Shipley proved that there is a stable set of engagements for any set of preferences and the first link above gives their algorithm for finding a set of stable engagements.
Task Specifics
Given ten males:
abe, bob, col, dan, ed, fred, gav, hal, ian, jon
And ten females:
abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan
And a complete list of ranked preferences, where the most liked is to the left:
abe: abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay bob: cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay col: hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan dan: ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi ed: jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay fred: bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay gav: gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay hal: abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee ian: hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve jon: abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope abi: bob, fred, jon, gav, ian, abe, dan, ed, col, hal bea: bob, abe, col, fred, gav, dan, ian, ed, jon, hal cath: fred, bob, ed, gav, hal, col, ian, abe, dan, jon dee: fred, jon, col, abe, ian, hal, gav, dan, bob, ed eve: jon, hal, fred, dan, abe, gav, col, ed, ian, bob fay: bob, abe, ed, ian, jon, dan, fred, gav, col, hal gay: jon, gav, hal, fred, bob, abe, col, ed, dan, ian hope: gav, jon, bob, abe, ian, dan, hal, ed, col, fred ivy: ian, col, hal, gav, fred, bob, abe, ed, jon, dan jan: ed, hal, gav, abe, bob, jon, col, ian, fred, dan
- Use the Gale Shapley algorithm to find a stable set of engagements
- Perturb this set of engagements to form an unstable set of engagements then check this new set for stability.
References
- The Stable Marriage Problem. (Eloquent description and background information).
- Gale-Shapley Algorithm Demonstration.
D
D v.2, adapted from the Python and Java versions. <lang d>import std.stdio: writeln, writefln; import std.array: popFront; import std.algorithm: indexOf, swap; import std.string: split, splitlines;
string[string] matchmaker(const string[][string] guyPrefers,
const string[][string] girlPrefers) {
string[string] engagedTo;
string[] freeGuys = guyPrefers.keys;
while (freeGuys.length) {
const auto string thisGuy = freeGuys[0];
freeGuys.popFront();
const auto thisGuyPrefers = guyPrefers[thisGuy];
foreach (girl; thisGuyPrefers) {
if (girl !in engagedTo) { // girl is free
engagedTo[girl] = thisGuy;
break;
} else {
string otherGuy = engagedTo[girl];
const string[] thisGirlPrefers = girlPrefers[girl];
if (thisGirlPrefers.indexOf(thisGuy) < thisGirlPrefers.indexOf(otherGuy)) {
// this girl prefers this guy to the guy she's engagedTo to
engagedTo[girl] = thisGuy;
freeGuys ~= otherGuy;
break;
}
// else no change, keep looking for this guy
}
}
}
return engagedTo;
}
bool check(bool doPrint=false)(const string[string] engagedTo,
const string[][string] guyPrefers,
const string[][string] galPrefers) {
enum MSG = "%s likes %s better than %s and %s likes %s better than their current partner";
string[string] inverseEngaged;
foreach (k, v; engagedTo)
inverseEngaged[v] = k;
foreach (she, he; engagedTo) {
const auto sheLikes = galPrefers[she];
const auto sheLikesBetter = sheLikes[0 .. sheLikes.indexOf(he)];
const auto heLikes = guyPrefers[he];
const auto heLikesBetter = heLikes[0 .. heLikes.indexOf(she)];
foreach (guy; sheLikesBetter) {
const auto guysGirl = inverseEngaged[guy];
const auto guyLikes = guyPrefers[guy];
if (guyLikes.indexOf(guysGirl) > guyLikes.indexOf(she)) {
static if (doPrint)
writefln(MSG, she, guy, he, guy, she);
return false;
}
}
foreach (gal; heLikesBetter) {
const auto girlsGuy = engagedTo[gal];
const auto galLikes = galPrefers[gal];
if (galLikes.indexOf(girlsGuy) > galLikes.indexOf(he)) {
static if (doPrint)
writefln(MSG, he, gal, she, gal, he);
return false;
}
}
}
return true;
}
void main() {
auto guyData = "abe abi eve cath ivy jan dee fay bea hope gay
bob cath hope abi dee eve fay bea jan ivy gay
col hope eve abi dee bea fay ivy gay cath jan
dan ivy fay dee gay hope eve jan bea cath abi
ed jan dee bea cath fay eve abi ivy hope gay
fred bea abi dee gay eve ivy cath jan hope fay
gav gay eve ivy bea cath abi dee hope jan fay
hal abi eve hope fay ivy cath jan bea gay dee
ian hope cath dee gay bea abi fay ivy jan eve
jon abi fay jan gay eve bea dee cath ivy hope";
auto galData = "abi bob fred jon gav ian abe dan ed col hal
bea bob abe col fred gav dan ian ed jon hal
cath fred bob ed gav hal col ian abe dan jon
dee fred jon col abe ian hal gav dan bob ed
eve jon hal fred dan abe gav col ed ian bob
fay bob abe ed ian jon dan fred gav col hal
gay jon gav hal fred bob abe col ed dan ian
hope gav jon bob abe ian dan hal ed col fred
ivy ian col hal gav fred bob abe ed jon dan
jan ed hal gav abe bob jon col ian fred dan";
string[][string] guyPrefers, galPrefers;
foreach (line; guyData.splitlines())
guyPrefers[split(line)[0]] = split(line)[1..$];
foreach (line; galData.splitlines())
galPrefers[split(line)[0]] = split(line)[1..$];
writeln("Engagements:");
auto engagedTo = matchmaker(guyPrefers, galPrefers);
writeln("\nCouples:");
string[] parts;
foreach (k; engagedTo.keys.sort)
writefln("%s is engagedTo to %s", k, engagedTo[k]);
writeln();
bool c = check!(true)(engagedTo, guyPrefers, galPrefers);
writeln("Marriages are ", c ? "stable" : "unstable");
writeln("\n\nSwapping two fiances to introduce an error");
auto gals = galPrefers.keys.sort;
swap(engagedTo[gals[0]], engagedTo[gals[1]]);
foreach (gal; gals[0 .. 2])
writefln(" %s is now engagedTo to %s", gal, engagedTo[gal]);
writeln();
c = check!(true)(engagedTo, guyPrefers, galPrefers);
writeln("Marriages are ", c ? "stable" : "unstable");
}</lang> Output:
Engagements: Couples: abi is engagedTo to jon bea is engagedTo to fred cath is engagedTo to bob dee is engagedTo to col eve is engagedTo to hal fay is engagedTo to dan gay is engagedTo to gav hope is engagedTo to ian ivy is engagedTo to abe jan is engagedTo to ed Marriages are stable Swapping two fiances to introduce an error abi is now engagedTo to fred bea is now engagedTo to jon fred likes bea better than abi and bea likes fred better than their current partner Marriages are unstable
Java
This is not a direct translation of Python, but it's fairly close (especially the stability check). <lang java5>import java.util.Arrays; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.TreeMap;
public class Stable {
static List<String> guys = Arrays.asList(
new String[]{"abe", "bob", "col", "dan", "ed", "fred", "gav", "hal", "ian", "jon"});
static List<String> girls = Arrays.asList(
new String[]{"abi", "bea", "cath", "dee", "eve", "fay", "gay", "hope", "ivy", "jan"});
static Map<String, List<String>> guyPrefers = new HashMap<String, List<String>>(){{
put("abe", Arrays.asList("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"));
put("bob", Arrays.asList("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"));
put("col", Arrays.asList("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"));
put("dan", Arrays.asList("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"));
put("ed", Arrays.asList("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"));
put("fred", Arrays.asList("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"));
put("gav", Arrays.asList("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"));
put("hal", Arrays.asList("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"));
put("ian", Arrays.asList("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"));
put("jon", Arrays.asList("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"));
}};
static Map<String, List<String>> girlPrefers = new HashMap<String, List<String>>(){{
put("abi", Arrays.asList("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"));
put("bea", Arrays.asList("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"));
put("cath", Arrays.asList("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"));
put("dee", Arrays.asList("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"));
put("eve", Arrays.asList("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"));
put("fay", Arrays.asList("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"));
put("gay", Arrays.asList("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"));
put("hope", Arrays.asList("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"));
put("ivy", Arrays.asList("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"));
put("jan", Arrays.asList("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"));
}};
public static void main(String[] args){
Map<String, String> matches = match(guys, guyPrefers, girlPrefers);
for(Map.Entry<String, String> couple:matches.entrySet()){
System.out.println(couple.getKey() + " is engaged to " + couple.getValue());
}
if(checkMatches(guys, girls, matches, guyPrefers, girlPrefers)){
System.out.println("Marriages are stable");
}else{
System.out.println("Marriages are unstable");
}
String tmp = matches.get(girls.get(0));
matches.put(girls.get(0), matches.get(girls.get(1)));
matches.put(girls.get(1), tmp);
System.out.println(girls.get(0) +" and " + girls.get(1) + " have switched partners");
if(checkMatches(guys, girls, matches, guyPrefers, girlPrefers)){
System.out.println("Marriages are stable");
}else{
System.out.println("Marriages are unstable");
}
}
private static Map<String, String> match(List<String> guys,
Map<String, List<String>> guyPrefers, Map<String, List<String>> girlPrefers){
Map<String, String> engagedTo = new TreeMap<String, String>();
List<String> freeGuys = new LinkedList<String>();
freeGuys.addAll(guys);
while(!freeGuys.isEmpty()){
String thisGuy = freeGuys.remove(0); //get a load of THIS guy
List<String> thisGuyPrefers = guyPrefers.get(thisGuy);
for(String girl:thisGuyPrefers){
if(engagedTo.get(girl) == null){//girl is free
engagedTo.put(girl, thisGuy); //awww
break;
}else{
String otherGuy = engagedTo.get(girl);
List<String> thisGirlPrefers = girlPrefers.get(girl);
if(thisGirlPrefers.indexOf(thisGuy) < thisGirlPrefers.indexOf(otherGuy)){
//this girl prefers this guy to the guy she's engaged to
engagedTo.put(girl, thisGuy);
freeGuys.add(otherGuy);
break;
}//else no change...keep looking for this guy
}
}
}
return engagedTo;
}
private static boolean checkMatches(List<String> guys, List<String> girls,
Map<String, String> matches, Map<String, List<String>> guyPrefers,
Map<String, List<String>> girlPrefers) {
if(!matches.keySet().containsAll(girls)){
return false;
}
if(!matches.values().containsAll(guys)){
return false;
}
Map<String, String> invertedMatches = new TreeMap<String, String>();
for(Map.Entry<String, String> couple:matches.entrySet()){
invertedMatches.put(couple.getValue(), couple.getKey());
}
for(Map.Entry<String, String> couple:matches.entrySet()){
List<String> shePrefers = girlPrefers.get(couple.getKey());
List<String> sheLikesBetter = new LinkedList<String>();
for(int i = 0; i < shePrefers.indexOf(couple.getValue());i++){
sheLikesBetter.add(shePrefers.get(i));
}
List<String> hePrefers = guyPrefers.get(couple.getValue());
List<String> heLikesBetter = new LinkedList<String>();
for(int i = 0; i < hePrefers.indexOf(couple.getKey());i++){
heLikesBetter.add(hePrefers.get(i));
}
for(String guy : sheLikesBetter){
String guysFinace = invertedMatches.get(guy);
List<String> thisGuyPrefers = guyPrefers.get(guy);
if(thisGuyPrefers.indexOf(guysFinace) > thisGuyPrefers.indexOf(couple.getKey())){
System.out.printf("%s likes %s better than %s and %s likes %s better than their current partner\n",
couple.getKey(), guy, couple.getValue(), guy, couple.getKey());
return false;
}
}
for(String girl : heLikesBetter){
String girlsFinace = matches.get(girl);
List<String> thisGirlPrefers = girlPrefers.get(girl);
if(thisGirlPrefers.indexOf(girlsFinace) > thisGirlPrefers.indexOf(couple.getValue())){
System.out.printf("%s likes %s better than %s and %s likes %s better than their current partner\n",
couple.getValue(), girl, couple.getKey(), girl, couple.getValue());
return false;
}
}
}
return true;
}
}</lang> Output:
abi is engaged to jon bea is engaged to fred cath is engaged to bob dee is engaged to col eve is engaged to hal fay is engaged to dan gay is engaged to gav hope is engaged to ian ivy is engaged to abe jan is engaged to ed Marriages are stable abi and bea have switched partners fred likes bea better than abi and bea likes fred better than their current partner Marriages are unstable
Python
<lang python>import copy from collections import defaultdict
guys = 'abe bob col dan ed fred gav hal ian jon'.strip().split() gals = 'abi bea cath dee eve fay gay hope ivy jan'.strip().split()
guyprefers = {'abe': ['abi', 'eve', 'cath', 'ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay'],
'bob': ['cath', 'hope', 'abi', 'dee', 'eve', 'fay', 'bea', 'jan', 'ivy', 'gay'], 'col': ['hope', 'eve', 'abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan'], 'dan': ['ivy', 'fay', 'dee', 'gay', 'hope', 'eve', 'jan', 'bea', 'cath', 'abi'], 'ed': ['jan', 'dee', 'bea', 'cath', 'fay', 'eve', 'abi', 'ivy', 'hope', 'gay'], 'fred': ['bea', 'abi', 'dee', 'gay', 'eve', 'ivy', 'cath', 'jan', 'hope', 'fay'], 'gav': ['gay', 'eve', 'ivy', 'bea', 'cath', 'abi', 'dee', 'hope', 'jan', 'fay'], 'hal': ['abi', 'eve', 'hope', 'fay', 'ivy', 'cath', 'jan', 'bea', 'gay', 'dee'], 'ian': ['hope', 'cath', 'dee', 'gay', 'bea', 'abi', 'fay', 'ivy', 'jan', 'eve'], 'jon': ['abi', 'fay', 'jan', 'gay', 'eve', 'bea', 'dee', 'cath', 'ivy', 'hope']}
galprefers = {'abi': ['bob', 'fred', 'jon', 'gav', 'ian', 'abe', 'dan', 'ed', 'col', 'hal'],
'bea': ['bob', 'abe', 'col', 'fred', 'gav', 'dan', 'ian', 'ed', 'jon', 'hal'], 'cath': ['fred', 'bob', 'ed', 'gav', 'hal', 'col', 'ian', 'abe', 'dan', 'jon'], 'dee': ['fred', 'jon', 'col', 'abe', 'ian', 'hal', 'gav', 'dan', 'bob', 'ed'], 'eve': ['jon', 'hal', 'fred', 'dan', 'abe', 'gav', 'col', 'ed', 'ian', 'bob'], 'fay': ['bob', 'abe', 'ed', 'ian', 'jon', 'dan', 'fred', 'gav', 'col', 'hal'], 'gay': ['jon', 'gav', 'hal', 'fred', 'bob', 'abe', 'col', 'ed', 'dan', 'ian'], 'hope': ['gav', 'jon', 'bob', 'abe', 'ian', 'dan', 'hal', 'ed', 'col', 'fred'], 'ivy': ['ian', 'col', 'hal', 'gav', 'fred', 'bob', 'abe', 'ed', 'jon', 'dan'], 'jan': ['ed', 'hal', 'gav', 'abe', 'bob', 'jon', 'col', 'ian', 'fred', 'dan']}
def check(engaged):
inverseengaged = dict((v,k) for k,v in engaged.items())
for she, he in engaged.items():
shelikes = galprefers[she]
shelikesbetter = shelikes[0:shelikes.index(he)]
helikes = guyprefers[he]
helikesbetter = helikes[0:helikes.index(she)]
for guy in shelikesbetter:
guysgirl = inverseengaged[guy]
guylikes = guyprefers[guy]
if guylikes.index(guysgirl) > guylikes.index(she):
print("%s likes %s better than %s and %s likes %s better than their current partner"
% (she, guy, he, guy, she))
return False
for gal in helikesbetter:
girlsguy = engaged[gal]
gallikes = galprefers[gal]
if gallikes.index(girlsguy) > gallikes.index(he):
print("%s likes %s better than %s and %s likes %s better than their current partner"
% (he, gal, she, gal, he))
return False
return True
def matchmaker():
guysfree = guys[:]
engaged = defaultdict(str)
guyprefers2 = copy.deepcopy(guyprefers)
galprefers2 = copy.deepcopy(galprefers)
while guysfree:
guy = guysfree.pop(0)
guyslist = guyprefers2[guy]
gal = guyslist.pop(0)
fiance = engaged[gal]
if not fiance:
# She's free
engaged[gal] = guy
print(" %s and %s" % (guy, gal))
else:
# The bounder proposes to an engaged lass!
galslist = galprefers2[gal]
if galslist.index(fiance) > galslist.index(guy):
# She prefers new guy
engaged[gal] = guy
print(" %s dumped %s for %s" % (gal, fiance, guy))
if guyprefers2[fiance]:
# Ex has more girls to try
guysfree.append(fiance)
else:
# She is fsithful to old fiance
if guyslist:
# Look again
guysfree.append(guy)
return engaged
print('\nEngagements:')
engaged = matchmaker()
print('\nCouples:') print(' ' + ',\n '.join('%s is engaged to %s' % couple
for couple in sorted(engaged.items())))
print() print('Engagement stability check PASSED'
if check(engaged) else 'Engagement stability check FAILED')
print('\n\nSwapping two fiances to introduce an error') engaged[gals[0]], engaged[gals[1]] = engaged[gals[1]], engaged[gals[0]] for gal in gals[:2]:
print(' %s is now engaged to %s' % (gal, engaged[gal]))
print() print('Engagement stability check PASSED'
if check(engaged) else 'Engagement stability check FAILED')</lang>
Sample Output
Engagements: abe and abi bob and cath col and hope dan and ivy ed and jan fred and bea gav and gay hope dumped col for ian abi dumped abe for jon hal and eve col and dee ivy dumped dan for abe dan and fay Couples: abi is engaged to jon, bea is engaged to fred, cath is engaged to bob, dee is engaged to col, eve is engaged to hal, fay is engaged to dan, gay is engaged to gav, hope is engaged to ian, ivy is engaged to abe, jan is engaged to ed Engagement stability check PASSED Swapping two fiances to introduce an error abi is now engaged to fred bea is now engaged to jon fay likes jon better than dan and jon likes fay better than their current partner Engagement stability check FAILED
Tcl
<lang tcl>package require Tcl 8.5
- Functions as aliases to standard commands
interp alias {} tcl::mathfunc::pos {} ::lsearch -exact interp alias {} tcl::mathfunc::nonempty {} ::llength
- The stability check
proc check engaged {
global preferences
set inverse [lreverse $engaged]
dict for {she he} $engaged {
set shelikes [dict get $preferences $she] set shelikesbetter [lrange $shelikes 0 [expr {pos($shelikes,$he)}]] set helikes [dict get $preferences $he] set helikesbetter [lrange $helikes 0 [expr {pos($helikes,$she)}]] foreach guy $shelikesbetter { set guysgirl [dict get $inverse $guy] set guylikes [dict get $preferences $guy] if {pos($guylikes,$guysgirl) > pos($guylikes,$she)} { puts "$she likes $guy better than $he and $he likes $she better than their current partner" return 0 } } foreach gal $helikesbetter { set galsguy [dict get $engaged $gal] set gallikes [dict get $preferences $gal] if {pos($gallikes,$galsguy) > pos($gallikes,$he)} { puts "$he likes $gal better than $she and $she likes $he better than their current partner" return 0 } }
} return 1
}
- The match-making algorithm
proc matchmaker {} {
global guys gals preferences
set guysfree $guys
set engaged {}
array set p $preferences
while {nonempty($guysfree)} {
set guysfree [lassign $guysfree guy] set p($guy) [set guyslist [lassign $p($guy) gal]] if {![dict exists $engaged $gal]} { # She's free dict set engaged $gal $guy puts " $guy and $gal" continue } # The bounder proposes to an engaged lass! set fiance [dict get $engaged $gal] if {pos($p($gal), $fiance) > pos($p($gal), $guy)} { # She prefers the new guy dict set engaged $gal $guy puts " $gal dumped $fiance for $guy" set guy $fiance } if {nonempty($p($guy))} { lappend guysfree $guy }
} return $engaged
}
- Problem dataset
set guys {abe bob col dan ed fred gav hal ian jon} set gals {abi bea cath dee eve fay gay hope ivy jan} set preferences {
abe {abi eve cath ivy jan dee fay bea hope gay}
bob {cath hope abi dee eve fay bea jan ivy gay}
col {hope eve abi dee bea fay ivy gay cath jan}
dan {ivy fay dee gay hope eve jan bea cath abi}
ed {jan dee bea cath fay eve abi ivy hope gay}
fred {bea abi dee gay eve ivy cath jan hope fay}
gav {gay eve ivy bea cath abi dee hope jan fay}
hal {abi eve hope fay ivy cath jan bea gay dee}
ian {hope cath dee gay bea abi fay ivy jan eve}
jon {abi fay jan gay eve bea dee cath ivy hope}
abi {bob fred jon gav ian abe dan ed col hal}
bea {bob abe col fred gav dan ian ed jon hal}
cath {fred bob ed gav hal col ian abe dan jon}
dee {fred jon col abe ian hal gav dan bob ed}
eve {jon hal fred dan abe gav col ed ian bob}
fay {bob abe ed ian jon dan fred gav col hal}
gay {jon gav hal fred bob abe col ed dan ian}
hope {gav jon bob abe ian dan hal ed col fred}
ivy {ian col hal gav fred bob abe ed jon dan}
jan {ed hal gav abe bob jon col ian fred dan}
}
- The demonstration code
puts "Engagements:" set engaged [matchmaker]
puts "\nCouples:" set pfx "" foreach gal $gals {
puts -nonewline "$pfx $gal is engaged to [dict get $engaged $gal]" set pfx ",\n"
} puts "\n" puts "Engagement stability check [lindex {FAILED PASSED} [check $engaged]]"
puts "\n\nSwapping two fiances to introduce an error" set tmp [dict get $engaged [lindex $gals 0]] dict set engaged [lindex $gals 0] [dict get $engaged [lindex $gals 1]] dict set engaged [lindex $gals 1] $tmp foreach gal [lrange $gals 0 1] {
puts " $gal is now engaged to [dict get $engaged $gal]"
} puts "" puts "Engagement stability check [lindex {FAILED PASSED} [check $engaged]]"</lang> Sample output:
Engagements: abe and abi bob and cath col and hope dan and ivy ed and jan fred and bea gav and gay hope dumped col for ian abi dumped abe for jon hal and eve col and dee ivy dumped dan for abe dan and fay Couples: abi is engaged to jon, bea is engaged to fred, cath is engaged to bob, dee is engaged to col, eve is engaged to hal, fay is engaged to dan, gay is engaged to gav, hope is engaged to ian, ivy is engaged to abe, jan is engaged to ed Engagement stability check PASSED Swapping two fiances to introduce an error abi is now engaged to fred bea is now engaged to jon fred likes bea better than abi and abi likes fred better than their current partner Engagement stability check FAILED