Stable marriage problem: Difference between revisions

Line 540:

Marriages are unstable</pre>

===Alternative version===

<lang d>import std.stdio, std.algorithm, std.array;

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

const menData = [

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

⚫

["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"]

];

alias M[][F] PrefMapF;

const womenData = [

alias F[][M] PrefMapM;

⚫

["abi", "bob","fred","jon","gav","ian","abe","dan","ed","col","hal"],

⚫

alias M[F] Couples;

⚫

["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"]

];

immutable PrefMapF womenPref;

alias string[] PrefList;

immutable PrefMapM menPref;

alias PrefList[string] PrefMap;

⚫

alias ~~string~~[~~string~~] Couples;

static this() {

with (F) with (M) {

⚫

womenPref = [

⚫

abi: [bob, fred, jon, gav, ian, abe, dan, ed, col, hal],

⚫

bea: [bob, abe, col, fred, gav, dan, ian, ed, jon, hal],

⚫

cath: [fred, bob, ed, gav, hal, col, ian, abe, dan, jon],

⚫

dee: [fred, jon, col, abe, ian, hal, gav, dan, bob, ed],

⚫

eve: [jon, hal, fred, dan, abe, gav, col, ed, ian, bob],

⚫

fay: [bob, abe, ed, ian, jon, dan, fred, gav, col, hal],

⚫

gay: [jon, gav, hal, fred, bob, abe, col, ed, dan, ian],

⚫

hope: [gav, jon, bob, abe, ian, dan, hal, ed, col, fred],

⚫

ivy: [ian, col, hal, gav, fred, bob, abe, ed, jon, dan],

⚫

jan: [ed, hal, gav, abe, bob, jon, col, ian, fred, dan]

⚫

];

menPref = [

⚫

abe: [abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay],

⚫

bob: [cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay],

⚫

col: [hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan],

⚫

dan: [ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi],

⚫

ed: [jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay],

⚫

fred: [bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay],

⚫

gav: [gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay],

⚫

hal: [abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee],

⚫

ian: [hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve],

⚫

jon: [abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope]

];

⚫

}

/// Does 'first' appear before 'second' in preference list?

bool prefers(~~in PrefList~~ prefer, ~~in string~~ first, ~~in string~~ second) pure nothrow {

bool prefers(T)(const(T[]) prefer, const(T) first, const(T) second) pure nothrow

if (is(T == F) || is(T == M)) {

foreach (p; prefer) {

if (p == first) return true;

Line 582:

Line 592:

}

void checkStability(in Couples engaged, in ~~PrefMap~~ menPref, in ~~PrefMap~~ womenPref) {

void checkStability(in Couples engaged, in PrefMapM menPref, in PrefMapF womenPref) {

writeln("Stablility:");

bool stable = true;

Line 605:

Line 615:

void main() {

⚫

M[] bachelors = sort(menPref.keys).release(); // no queue in Phobos

⚫

~~PrefMap~~ ~~menPref,~~ womenPref;

⚫

Couples engaged;

⚫

~~string~~[] bachelors; // no queue in Phobos

// init data structures

foreach (i; 0 .. 10) { // person

foreach (j; 1 .. 11) { // preference

menPref[menData[i][0]] ~= menData[i][j];

womenPref[womenData[i][0]] ~= womenData[i][j];

⚫

}

bachelors ~= menData[i][0];

⚫

}

⚫

Couples engaged; ~~// <woman,man>~~

writeln("Matchmaking:");

Line 650:

Line 649:

writeln("Perturb:");

swap(engaged["abi"], engaged["bea"]);

swap(engaged[F.abi], engaged[F.bea]);

writeln("\tengage abi with ", engaged["abi"], " and bea with ", engaged["bea"]);

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

checkStability(engaged, menPref, womenPref);

Line 671:

Line 670:

Engagements:

abi and jon

⚫

hope and ian

ivy and abe

eve and hal

~~dee~~ and ~~col~~

jan and ed

⚫

~~cath~~ and ~~bob~~

bea and fred

fay and dan

~~jan~~ and ed

cath and bob

gay and gav

⚫

hope and ian

⚫

dee and col

Stablility:

(all marriages stable)