Rosetta Code

Stable marriage problem: Difference between revisions

Page Discussion

Stable marriage problem (view source)

Revision as of 11:51, 28 January 2017

136 bytes removed ,  7 years ago
→‎{{header|Scala}}: update
(→‎{{header|Scala}}: unused import removal)
Line 5,655:
{{trans|Java}}
<lang scala>object SMP extends App {
private def runcheckMarriages(): Unit {=
valif matches = matching(check)
matches.foreach { e => println(s"${e._1} is engaged to ${e._2}") }▼
if (checkMatches(matches))
println("Marriages are stable")
else
println("Marriages are unstable")
 
private def swap() {
val girl1 = girls.head
val girl2 = girls(1)
val tmp = girl2 -> matches(girl1)
matches += girl1 -> matches(girl2)
matches += girl2 -> tmp
println(girl1 + " and " + girl2 + " have switched partners")
if (checkMatches(matches))
println("Marriages are stable")
else▼
println("Marriages are unstable")
}
 
private type TM = scala.collection.mutable.TreeMap[String, String]
 
private def matchingcheck: Boolean = {
val engagements = new TM▼
val freeGuys = scala.collection.mutable.Queue.empty ++ guys▼
while (freeGuys.nonEmpty) {▼
val guy = freeGuys.dequeue()▼
val guy_p = guyPrefers(guy)▼
var break = false▼
for (girl <- guy_p)▼
if (!break)▼
if (!engagements.contains(girl)) {▼
engagements += girl -> guy▼
break = true▼
}▼
else {▼
val other_guy = engagements(girl)▼
val girl_p = girlPrefers(girl)▼
if (girl_p.indexOf(guy) < girl_p.indexOf(other_guy)) {▼
engagements += girl -> guy▼
freeGuys += other_guy▼
break = true▼
}▼
}▼
}▼
 
engagements▼
}▼
 
private def checkMatches(matches: scala.collection.Map[String, String]): Boolean = {
if (!girls.toSet.subsetOf(matches.keySet) || !guys.toSet.subsetOf(matches.values.toSet))
return false
 
val invertedMatches = new TM
matches. foreach { invertedMatches += _.swap }
 
for ((k, v) <- matches) {
Line 5,760 ⟶ 5,728:
"ivy" -> List("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
"jan" -> List("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"))
▲ }
private lazy val matches = {
▲ val engagements = new TM
▲ val freeGuys = scala.collection.mutable.Queue.empty ++ guys
▲ while (freeGuys.nonEmpty) {
▲ val guy = freeGuys.dequeue()
▲ val guy_p = guyPrefers(guy)
▲ var break = false
▲ for (girl <- guy_p)
▲ if (!break)
▲ if (!engagements.contains(girl)) {
▲ engagements(girl) += girl -> guy
▲ break = true
▲ }
▲ else {
▲ val other_guy = engagements(girl)
▲ val girl_p = girlPrefers(girl)
▲ if (girl_p.indexOf(guy) < girl_p.indexOf(other_guy)) {
▲ engagements(girl) += girl -> guy
▲ freeGuys += other_guy
▲ break = true
▲ }
▲ }
▲ else}
 
▲ matches.engagements foreach { e => println(s"${e._1} is engaged to ${e._2}") }
run()▼
▲ engagements
▲ }
checkMarriages()
▲ runswap()
checkMarriages()
}</lang>
{{out}}
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/154433"