Anonymous user
Stable marriage problem: Difference between revisions
Second D version, from the C++ one
(Second D version, from the C++ one) |
|||
Line 384:
=={{header|D}}==
<lang d>import std.stdio, std.array, std.algorithm, std.string;
Line 539:
fred likes bea better than abi and bea likes fred better than their current partner
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#}}==
| |||