Stable marriage problem: Difference between revisions

Content added Content deleted
Line 5,654: Line 5,654:
=={{header|Scala}}==
=={{header|Scala}}==
{{trans|Java}}
{{trans|Java}}
<lang scala>import java.util._
<lang scala>import scala.collection.mutable.AbstractMap
import scala.collection.JavaConversions._
import scala.collection.mutable.HashMap
import scala.collection.mutable.HashSet
import scala.collection.mutable.Queue
import scala.collection.mutable.TreeMap


object SMP extends App {
object SMP extends App {
def run() {
def run() {
val matches = matching(guys, guyPrefers, girlPrefers)
Seq("abe" -> Array("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
matches.foreach { e => println(s"${e._1} is engaged to ${e._2}") }
"bob" -> Array("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
"col" -> Array("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
println("Marriages are stable")
"dan" -> Array("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"),
else
"ed" -> Array("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"),
println("Marriages are unstable")
"fred" -> Array("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"),
"gav" -> Array("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"),
"hal" -> Array("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"),
"ian" -> Array("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
"jon" -> Array("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"))
.foreach { e => guyPrefers.put(e._1, e._2.toList) }


val girl1 = girls.head
Seq("abi" -> Array("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
val girl2 = girls(1)
"bea" -> Array("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
val tmp = matches(girl1)
"cath" -> Array("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
matches += girl1 -> matches(girl2)
"dee" -> Array("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"),
matches += girl2 -> tmp
"eve" -> Array("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"),
"fay" -> Array("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"),
println(girl1 + " and " + girl2 + " have switched partners")
if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
"gay" -> Array("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"),
println("Marriages are stable")
"hope" -> Array("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"),
else
"ivy" -> Array("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
println("Marriages are unstable")
"jan" -> Array("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"))
}
.foreach { e => girlPrefers.put(e._1, e._2.toList) }


val matches = matching(guys, guyPrefers, girlPrefers)
private def matching(guys: Seq[String],
guyPrefers: AbstractMap[String, List[String]],
matches.foreach { e => println(s"${e._1} is engaged to ${e._2}") }
girlPrefers: AbstractMap[String, List[String]]): TreeMap[String, String] = {
if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
val engagements = new TreeMap[String, String]
println("Marriages are stable")
val freeGuys = new Queue[String]
else
freeGuys ++= guys
println("Marriages are unstable")
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
}
}
}


val tmp = matches(girls(0))
engagements
matches += girls(0) -> matches(girls(1))
matches += girls(1) -> tmp
println(girls(0) + " and " + girls(1) + " have switched partners")
if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
println("Marriages are stable")
else
println("Marriages are unstable")
}

private def matching(guys: Iterable[String],
guyPrefers: Map[String, List[String]],
girlPrefers: Map[String, List[String]]): Map[String, String] = {
val engagements = new TreeMap[String, String]
val freeGuys = new LinkedList[String](guys)
while (!freeGuys.isEmpty) {
val guy = freeGuys.remove(0)
val guy_p = guyPrefers(guy)
var break = false
for (girl <- guy_p)
if (!break)
if (!engagements.containsKey(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
}
}
}
}


private def checkMatches(guys: Seq[String], girls: Seq[String],
engagements
matches: AbstractMap[String, String],
}
guyPrefers: AbstractMap[String, List[String]],
girlPrefers: AbstractMap[String, List[String]]): Boolean = {
if (!girls.toSet.subsetOf(matches.keySet) || !guys.toSet.subsetOf(HashSet() ++= matches.values))
return false


private def checkMatches(guys: Iterable[String], girls: Iterable[String],
val invertedMatches = new TreeMap[String, String]
matches.foreach { invertedMatches += _.swap }
matches: Map[String, String],
guyPrefers: Map[String, List[String]],
girlPrefers: Map[String, List[String]]): Boolean = {
if (!matches.keySet.containsAll(girls) || !matches.values.containsAll(guys))
return false


for ((k, v) <- matches) {
val invertedMatches = new TreeMap[String, String]
val shePrefers = girlPrefers(k)
matches.foreach { invertedMatches += _.swap }
val sheLikesBetter = Queue() ++= shePrefers.slice(0, shePrefers.indexOf(v))
val hePrefers = guyPrefers(v)
val heLikesBetter = Queue() ++= hePrefers.slice(0, hePrefers.indexOf(k))


for ((k, v) <- matches) {
for (guy <- sheLikesBetter) {
val shePrefers = girlPrefers(k)
val fiance = invertedMatches(guy)
val sheLikesBetter = new LinkedList[String]
val guy_p = guyPrefers(guy)
sheLikesBetter.addAll(shePrefers.subList(0, shePrefers.indexOf(v)))
if (guy_p.indexOf(fiance) > guy_p.indexOf(k)) {
println(s"$k likes $guy better than $v and $guy likes $k better than their current partner")
val hePrefers = guyPrefers(v)
return false
val heLikesBetter = new LinkedList[String]
}
heLikesBetter.addAll(hePrefers.subList(0, hePrefers.indexOf(k)))
}


for (guy <- sheLikesBetter) {
for (girl <- heLikesBetter) {
val fiance = invertedMatches(guy)
val fiance = matches(girl)
val guy_p = guyPrefers(guy)
val girl_p = girlPrefers(girl)
if (guy_p.indexOf(fiance) > guy_p.indexOf(k)) {
if (girl_p.indexOf(fiance) > girl_p.indexOf(v)) {
println(s"$k likes $guy better than $v and $guy likes $k better than their current partner")
println(s"$v likes $girl better than $k and $girl likes $v better than their current partner")
return false
return false
}
}
}
}

for (girl <- heLikesBetter) {
val fiance = matches(girl)
val girl_p = girlPrefers(girl)
if (girl_p.indexOf(fiance) > girl_p.indexOf(v)) {
println(s"$v likes $girl better than $k and $girl likes $v better than their current partner")
return false
}
}
}
true
}
}
true
}


private val guys = "abe" :: "bob" :: "col" :: "dan" :: "ed" :: "fred" :: "gav" :: "hal" :: "ian" :: "jon" :: Nil
private val guys = "abe" :: "bob" :: "col" :: "dan" :: "ed" :: "fred" :: "gav" :: "hal" :: "ian" :: "jon" :: Nil
private val girls = "abi" :: "bea" :: "cath" :: "dee" :: "eve" :: "fay" :: "gay" :: "hope" :: "ivy" :: "jan" :: Nil
private val girls = "abi" :: "bea" :: "cath" :: "dee" :: "eve" :: "fay" :: "gay" :: "hope" :: "ivy" :: "jan" :: Nil
private val guyPrefers = new HashMap[String, List[String]]
private val guyPrefers = HashMap("abe" -> List("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
"bob" -> List("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
private val girlPrefers = new HashMap[String, List[String]]
"col" -> List("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
"dan" -> List("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"),
"ed" -> List("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"),
"fred" -> List("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"),
"gav" -> List("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"),
"hal" -> List("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"),
"ian" -> List("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
"jon" -> List("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"))
private val girlPrefers = HashMap("abi" -> List("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
"bea" -> List("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
"cath" -> List("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
"dee" -> List("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"),
"eve" -> List("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"),
"fay" -> List("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"),
"gay" -> List("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"),
"hope" -> List("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"),
"ivy" -> List("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
"jan" -> List("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"))


run()
run()
}</lang>
}</lang>
{{out}}
{{out}}
Retrieved from "https://rosettacode.org/wiki/Stable_marriage_problem"