Jump to content

Stable marriage problem: Difference between revisions

Stable marriage problem (view source)

Revision as of 03:05, 9 November 2011

126 bytes removed ,  12 years ago
Better D alternative version
(Second D version, from the C++ one)
(Better D alternative version)
Line 540:
Marriages are unstable</pre>
===Alternative version===
{{trans|C++}}
<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 stringM[stringF] 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) {
PrefMap menPref, 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 PrefListT)(const(T[]) prefer, in stringconst(T) first, in stringconst(T) second) pure nothrow {
if (is(T == F) || is(T == M)) {
foreach (p; prefer) {
if (p == first) return true;
Line 582 ⟶ 592:
}
 
void checkStability(in Couples engaged, in PrefMapPrefMapM menPref, in PrefMapPrefMapF womenPref) {
writeln("Stablility:");
bool stable = true;
Line 605 ⟶ 615:
 
void main() {
stringM[] bachelors = sort(menPref.keys).release(); // no queue in Phobos▼
▲ PrefMap menPref, womenPref;
Couples engaged; // <woman,man>▼
▲ 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 ⟶ 649:
 
writeln("Perturb:");
swap(engaged["F.abi"], engaged["F.bea"]);
writeln("\tengage abi with ", engaged["F.abi"], " and bea with ", engaged["F.bea"]);
 
checkStability(engaged, menPref, womenPref);
Line 671 ⟶ 670:
Engagements:
abi and jon
hope and ian▼
ivy and abe
eve and hal
deejan and coled
cath and bob▼
bea and fred
fay and dan
jancath and edbob
gay and gav
▲ hope and ian
▲ cathdee and bobcol
Stablility:
(all marriages stable)
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/154355"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information