Stable marriage problem: Difference between revisions

Line 5,655:

<lang scala>object SMP extends App {

def ~~run~~() {

private def checkMarriages(): Unit =

~~val~~ ~~matches = matching~~

if (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 = matches(girl1)

val tmp = girl2 -> matches(girl1)

matches += girl1 -> matches(girl2)

matches += ~~girl2 ->~~ tmp

matches += 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 ~~matching~~ = {

private def check: 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 }

matches foreach { invertedMatches += _.swap }

for ((k, v) <- matches) {

Line 5,760:

Line 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) = 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 foreach { e => println(s"${e._1} is engaged to ${e._2}") }

⚫

~~run~~()

⚫

engagements

⚫

}

checkMarriages()

⚫

swap()

checkMarriages()

}</lang>