Anonymous user
Stable marriage problem: Difference between revisions
→{{header|Groovy}}: new solution
(Better D alternative version) |
(→{{header|Groovy}}: new solution) |
||
Line 854:
</pre>
=={{header|Groovy}}==
{{trans|Java}} (more or less) Uses explicit maps for preference ranking rather than list position. Uses Man and Woman enumerated types instead of string names, in order to use compile time type and constant checking to help keep the playas straight without a scorecard.
"Stable Matching" Solution:
<lang groovy>import static Man.*
import static Woman.*
Map<Woman,Man> match(Map<Man,Map<Woman,Integer>> guysGalRanking, Map<Woman,Map<Man,Integer>> galsGuyRanking) {
Map<Woman,Man> engagedTo = new TreeMap()
List<Man> freeGuys = (Man.values()).clone()
while(freeGuys) {
Man thisGuy = freeGuys[0]
freeGuys -= thisGuy
List<Woman> guyChoices = Woman.values().sort{ she -> - guysGalRanking[thisGuy][she] }
for(Woman girl in guyChoices) {
if(! engagedTo[girl]) {
engagedTo[girl] = thisGuy
break
} else {
Man thatGuy = engagedTo[girl]
if (galsGuyRanking[girl][thisGuy] > galsGuyRanking[girl][thatGuy]) {
engagedTo[girl] = thisGuy
freeGuys << thatGuy
break
}
}
}
}
engagedTo
}</lang>
"Stability Checking" Solution:
(Could do more to eliminate common code. Maybe later.)
<lang groovy>boolean isStable(Map<Woman,Man> matches, Map<Man,Map<Woman,Integer>> guysGalRanking, Map<Woman,Map<Man,Integer>> galsGuyRanking) {
matches.collect{ girl, guy ->
int guysRank = galsGuyRanking[girl][guy]
List<Man> sheLikesBetter = Man.values().findAll{ he -> galsGuyRanking[girl][he] > guysRank }
for(Man otherGuy : sheLikesBetter) {
Woman otherGuyFiancee = matches.find{ pair -> pair.value == otherGuy }.key
if(guysGalRanking[otherGuy][girl] > guysGalRanking[otherGuy][otherGuyFiancee]) {
println """O. M. G. ... ${otherGuy} likes ${girl} better than ${otherGuyFiancee}, and ${girl} likes ${otherGuy} better than ${guy}!
I am TOTALLY 'shipping ${girl} and ${otherGuy} now!"""
return false
}
}
int galsRank = guysGalRanking[guy][girl]
List<Woman> heLikesBetter = Woman.values().findAll{ she -> guysGalRanking[guy][she] > galsRank }
for(Woman otherGal : heLikesBetter) {
Man otherGalFiance = matches[otherGal]
if(galsGuyRanking[otherGal][guy] > galsGuyRanking[otherGal][otherGalFiance]) {
println """O. M. G. ... ${otherGal} likes ${guy} better than ${otherGalFiance}, and ${guy} likes ${otherGal} better than ${girl}!
I am TOTALLY 'shipping ${guy} and ${otherGal} now!"""
return false
}
}
true
}.every()
}</lang>
Test (Stable and Perturbed):
<lang groovy>enum Man {
abe, bob, col, dan, ed, fred, gav, hal, ian, jon
}
enum Woman {
abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan
}
Map<Man,Map<Woman,Integer>> mansWomanRanking = [
(abe): [(abi):10, (eve):9, (cath):8, (ivy):7, (jan):6, (dee):5, (fay):4, (bea):3, (hope):2, (gay):1],
(bob): [(cath):10, (hope):9, (abi):8, (dee):7, (eve):6, (fay):5, (bea):4, (jan):3, (ivy):2, (gay):1],
(col): [(hope):10, (eve):9, (abi):8, (dee):7, (bea):6, (fay):5, (ivy):4, (gay):3, (cath):2, (jan):1],
(dan): [(ivy):10, (fay):9, (dee):8, (gay):7, (hope):6, (eve):5, (jan):4, (bea):3, (cath):2, (abi):1],
(ed): [(jan):10, (dee):9, (bea):8, (cath):7, (fay):6, (eve):5, (abi):4, (ivy):3, (hope):2, (gay):1],
(fred):[(bea):10, (abi):9, (dee):8, (gay):7, (eve):6, (ivy):5, (cath):4, (jan):3, (hope):2, (fay):1],
(gav): [(gay):10, (eve):9, (ivy):8, (bea):7, (cath):6, (abi):5, (dee):4, (hope):3, (jan):2, (fay):1],
(hal): [(abi):10, (eve):9, (hope):8, (fay):7, (ivy):6, (cath):5, (jan):4, (bea):3, (gay):2, (dee):1],
(ian): [(hope):10, (cath):9, (dee):8, (gay):7, (bea):6, (abi):5, (fay):4, (ivy):3, (jan):2, (eve):1],
(jon): [(abi):10, (fay):9, (jan):8, (gay):7, (eve):6, (bea):5, (dee):4, (cath):3, (ivy):2, (hope):1],
]
Map<Woman,List<Man>> womansManRanking = [
(abi): [(bob):10, (fred):9, (jon):8, (gav):7, (ian):6, (abe):5, (dan):4, (ed):3, (col):2, (hal):1],
(bea): [(bob):10, (abe):9, (col):8, (fred):7, (gav):6, (dan):5, (ian):4, (ed):3, (jon):2, (hal):1],
(cath):[(fred):10, (bob):9, (ed):8, (gav):7, (hal):6, (col):5, (ian):4, (abe):3, (dan):2, (jon):1],
(dee): [(fred):10, (jon):9, (col):8, (abe):7, (ian):6, (hal):5, (gav):4, (dan):3, (bob):2, (ed):1],
(eve): [(jon):10, (hal):9, (fred):8, (dan):7, (abe):6, (gav):5, (col):4, (ed):3, (ian):2, (bob):1],
(fay): [(bob):10, (abe):9, (ed):8, (ian):7, (jon):6, (dan):5, (fred):4, (gav):3, (col):2, (hal):1],
(gay): [(jon):10, (gav):9, (hal):8, (fred):7, (bob):6, (abe):5, (col):4, (ed):3, (dan):2, (ian):1],
(hope):[(gav):10, (jon):9, (bob):8, (abe):7, (ian):6, (dan):5, (hal):4, (ed):3, (col):2, (fred):1],
(ivy): [(ian):10, (col):9, (hal):8, (gav):7, (fred):6, (bob):5, (abe):4, (ed):3, (jon):2, (dan):1],
(jan): [(ed):10, (hal):9, (gav):8, (abe):7, (bob):6, (jon):5, (col):4, (ian):3, (fred):2, (dan):1],
]
// STABLE test
Map<Woman,Man> matches = match(mansWomanRanking, womansManRanking)
matches.each { w, m ->
println "${w} (his '${mansWomanRanking[m][w]}' girl) is engaged to ${m} (her '${womansManRanking[w][m]}' guy)"
}
assert matches.keySet() == Woman.values() as Set
assert matches.values() as Set == Man.values() as Set
println ''
assert isStable(matches, mansWomanRanking, womansManRanking)
// PERTURBED test
println 'Swapping partners now ...'
def temp = matches[abi]
matches[abi] = matches[bea]
matches[bea] = temp
matches.each { w, m ->
println "${w} (his '${mansWomanRanking[m][w]}' girl) is engaged to ${m} (her '${womansManRanking[w][m]}' guy)"
}
println ''
assert ! isStable(matches, mansWomanRanking, womansManRanking)</lang>
Output:
<pre>abi (his '10' girl) is engaged to jon (her '8' guy)
bea (his '10' girl) is engaged to fred (her '7' guy)
cath (his '10' girl) is engaged to bob (her '9' guy)
dee (his '7' girl) is engaged to col (her '8' guy)
eve (his '9' girl) is engaged to hal (her '9' guy)
fay (his '9' girl) is engaged to dan (her '5' guy)
gay (his '10' girl) is engaged to gav (her '9' guy)
hope (his '10' girl) is engaged to ian (her '6' guy)
ivy (his '7' girl) is engaged to abe (her '4' guy)
jan (his '10' girl) is engaged to ed (her '10' guy)
Swapping partners now ...
abi (his '9' girl) is engaged to fred (her '9' guy)
bea (his '5' girl) is engaged to jon (her '2' guy)
cath (his '10' girl) is engaged to bob (her '9' guy)
dee (his '7' girl) is engaged to col (her '8' guy)
eve (his '9' girl) is engaged to hal (her '9' guy)
fay (his '9' girl) is engaged to dan (her '5' guy)
gay (his '10' girl) is engaged to gav (her '9' guy)
hope (his '10' girl) is engaged to ian (her '6' guy)
ivy (his '7' girl) is engaged to abe (her '4' guy)
jan (his '10' girl) is engaged to ed (her '10' guy)
O. M. G. ... bea likes fred better than jon, and fred likes bea better than abi!
I am TOTALLY 'shipping fred and bea now!
O. M. G. ... fred likes bea better than abi, and bea likes fred better than jon!
I am TOTALLY 'shipping bea and fred now!
O. M. G. ... jon likes eve better than bea, and eve likes jon better than hal!
I am TOTALLY 'shipping eve and jon now!
O. M. G. ... jon likes fay better than bea, and fay likes jon better than dan!
I am TOTALLY 'shipping fay and jon now!
O. M. G. ... jon likes gay better than bea, and gay likes jon better than gav!
I am TOTALLY 'shipping gay and jon now!
</pre>
=={{header|Haskell}}==
| |||