Stable marriage problem: Difference between revisions
Content added Content deleted
(Second D version, from the C++ one) |
|||
Line 384: | Line 384: | ||
=={{header|D}}== |
=={{header|D}}== |
||
From the Python and Java versions: |
|||
<lang d>import std.stdio, std.array, std.algorithm, std.string; |
<lang d>import std.stdio, std.array, std.algorithm, std.string; |
||
Line 539: | Line 539: | ||
fred likes bea better than abi and bea likes fred better than their current partner |
fred likes bea better than abi and bea likes fred better than their current partner |
||
Marriages are unstable</pre> |
Marriages are unstable</pre> |
||
===Alternative version=== |
|||
{{trans|C++}} |
|||
<lang d>import std.stdio, std.algorithm, std.array; |
|||
const menData = [ |
|||
["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 womenData = [ |
|||
["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"] |
|||
]; |
|||
alias string[] PrefList; |
|||
alias PrefList[string] PrefMap; |
|||
alias string[string] Couples; |
|||
/// Does 'first' appear before 'second' in preference list? |
|||
bool prefers(in PrefList prefer, in string first, in string second) pure nothrow { |
|||
foreach (p; prefer) { |
|||
if (p == first) return true; |
|||
if (p == second) return false; |
|||
} |
|||
return false; // no preference |
|||
} |
|||
void checkStability(in Couples engaged, in PrefMap menPref, in PrefMap womenPref) { |
|||
writeln("Stablility:"); |
|||
bool stable = true; |
|||
foreach (bride, groom; engaged) { |
|||
const preflist = menPref[groom]; |
|||
foreach (pr; preflist) { |
|||
if (pr == bride) // he prefers his bride |
|||
break; |
|||
if (prefers(preflist, pr, bride) && // he prefers another woman |
|||
prefers(womenPref[pr], groom, engaged[pr])) { // other woman prefers him |
|||
writeln("\t", pr, " prefers ", groom, " over ", engaged[pr], |
|||
" and ", groom, " prefers ", pr, " over ", bride); |
|||
stable = false; |
|||
} |
|||
} |
|||
} |
|||
if (stable) |
|||
writeln("\t(all marriages stable)"); |
|||
} |
|||
void main() { |
|||
PrefMap menPref, womenPref; |
|||
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:"); |
|||
while (!bachelors.empty) { |
|||
immutable suitor = bachelors[0]; |
|||
bachelors = bachelors[1 .. $]; // no array pop front |
|||
const preflist = menPref[suitor]; |
|||
foreach (bride; preflist) { |
|||
if (bride !in engaged) { // she's available |
|||
writeln("\t", bride, " and ", suitor); |
|||
engaged[bride] = suitor; // hook up |
|||
break; |
|||
} |
|||
immutable groom = engaged[bride]; |
|||
if (prefers(womenPref[bride], suitor, groom)) { |
|||
writeln("\t", bride, " dumped ", groom, " for ", suitor); |
|||
bachelors ~= groom; // dump that zero |
|||
engaged[bride] = suitor; // get a hero |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
writeln("Engagements:"); |
|||
foreach (first, second; engaged) |
|||
writeln("\t", first, " and ", second); |
|||
checkStability(engaged, menPref, womenPref); |
|||
writeln("Perturb:"); |
|||
swap(engaged["abi"], engaged["bea"]); |
|||
writeln("\tengage abi with ", engaged["abi"], " and bea with ", engaged["bea"]); |
|||
checkStability(engaged, menPref, womenPref); |
|||
}</lang> |
|||
<pre>Matchmaking: |
|||
abi and abe |
|||
cath and bob |
|||
hope and col |
|||
ivy and dan |
|||
jan and ed |
|||
bea and fred |
|||
gay and gav |
|||
eve and hal |
|||
hope dumped col for ian |
|||
abi dumped abe for jon |
|||
dee and col |
|||
ivy dumped dan for abe |
|||
fay and dan |
|||
Engagements: |
|||
abi and jon |
|||
hope and ian |
|||
ivy and abe |
|||
eve and hal |
|||
dee and col |
|||
cath and bob |
|||
bea and fred |
|||
fay and dan |
|||
jan and ed |
|||
gay and gav |
|||
Stablility: |
|||
(all marriages stable) |
|||
Perturb: |
|||
engage abi with fred and bea with jon |
|||
Stablility: |
|||
bea prefers fred over jon and fred prefers bea over abi |
|||
fay prefers jon over dan and jon prefers fay over bea |
|||
gay prefers jon over gav and jon prefers gay over bea |
|||
eve prefers jon over hal and jon prefers eve over bea</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |