Stable marriage problem: Difference between revisions

Content added Content deleted
(added Ceylon)
Line 3,654: Line 3,654:


=={{header|Kotlin}}==
=={{header|Kotlin}}==
{{trans|Java}}
<lang scala>import java.util.*


<lang kotlin>
class People(val map: Map<String, Array<String>>) {
operator fun get(name: String) = map[name]
data class Person(val name: String) {
val preferences = mutableListOf<Person>()
var matchedTo: Person? = null


fun trySwap(p: Person) {
val names: List<String> by lazy { map.keys.toList() }
if (prefers(p)) {

matchedTo?.matchedTo = null
fun preferences(k: String, v: String): List<String> {
val prefers = get(k)!!
matchedTo = p
p.matchedTo = this
return ArrayList<String>(prefers.slice(0..prefers.indexOf(v)))
}
}

class EngagementRegistry() : TreeMap<String, String>() {
constructor(guys: People, girls: People) : this() {
val freeGuys = guys.names.toMutableList()
while (freeGuys.any()) {
val guy = freeGuys.removeAt(0) // get a load of THIS guy
val guy_p = guys[guy]!!
for (girl in guy_p)
if (this[girl] == null) {
this[girl] = guy // girl is free
break
} else {
val other = this[girl]!!
val girl_p = girls[girl]!!
if (girl_p.indexOf(guy) < girl_p.indexOf(other)) {
this[girl] = guy // this girl prefers this guy to the guy she's engaged to
freeGuys += other
break
} // else no change... keep looking for this guy
}
}
}
}
}


override fun toString(): String {
fun prefers(p: Person) = when (matchedTo) {
val s = StringBuilder()
null -> true
else -> preferences.indexOf(p) < preferences.indexOf(matchedTo!!)
for ((k, v) in this) s.append("$k is engaged to $v\n")
return s.toString()
}
}


fun analyse(guys: People, girls: People) {
fun showMatch() = "$name <=> ${matchedTo?.name}"
}
if (check(guys, girls))

println("Marriages are stable")
fun match(males: Collection<Person>) {
else
while (males.find { it.matchedTo == null }?.also { match(it) } != null) {
println("Marriages are unstable")
}
}
}


fun swap(girls: People, i: Int, j: Int) {
fun match(male: Person) {
while (male.matchedTo == null) {
val n1 = girls.names[i]
male.preferences.removeAt(0).trySwap(male)
val n2 = girls.names[j]
val g0 = this[n1]!!
val g1 = this[n2]!!
this[n1] = g1
this[n2] = g0
println("$n1 and $n2 have switched partners")
}
}
}


private fun check(guys: People, girls: People): Boolean {
fun isStableMatch(males: Collection<Person>, females: Collection<Person>): Boolean {
return males.all { isStableMatch(it, females) }
val guy_names = guys.names
}
val girl_names = girls.names
if (!keys.containsAll(girl_names) or !values.containsAll(guy_names))
return false


fun isStableMatch(male: Person, females: Collection<Person>): Boolean {
val invertedMatches = TreeMap<String, String>()
for ((k, v) in this) invertedMatches[v] = k


val likesBetter = females.filter { !male.preferences.contains(it) }
for ((k, v) in this) {
val stable = !likesBetter.any { it.prefers(male) }
val sheLikesBetter = girls.preferences(k, v)
val heLikesBetter = guys.preferences(v, k)
for (guy in sheLikesBetter) {
val fiance = invertedMatches[guy]
val guy_p = guys[guy]!!
if (guy_p.indexOf(fiance) > guy_p.indexOf(k)) {
println("$k likes $guy better than $v and $guy likes $k better than their current partner")
return false
}
}


for (girl in heLikesBetter) {
if (!stable) {
val fiance = get(girl)
println("#### Unstable pair: ${male.showMatch()}")
val girl_p = girls[girl]!!
if (girl_p.indexOf(fiance) > girl_p.indexOf(v)) {
println("$v likes $girl better than $k and $girl likes $v better than their current partner")
return false
}
}
}
return true
}
}
return stable
}
}



fun main(args: Array<String>) {
fun main(args: Array<String>) {
val inMales = mapOf(
val guys = People(mapOf("abe" to arrayOf("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
"bob" to arrayOf("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
"abe" to mutableListOf("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
"col" to arrayOf("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
"bob" to mutableListOf("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
"dan" to arrayOf("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"),
"col" to mutableListOf("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
"ed" to arrayOf("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"),
"dan" to mutableListOf("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"),
"fred" to arrayOf("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"),
"ed" to mutableListOf("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"),
"gav" to arrayOf("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"),
"fred" to mutableListOf("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"),
"hal" to arrayOf("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"),
"gav" to mutableListOf("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"),
"ian" to arrayOf("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
"hal" to mutableListOf("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"),
"jon" to arrayOf("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope")))
"ian" to mutableListOf("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
"jon" to mutableListOf("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"))


val inFemales = mapOf(
val girls = People(mapOf("abi" to arrayOf("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
"bea" to arrayOf("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
"abi" to listOf("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
"cath" to arrayOf("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
"bea" to listOf("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
"dee" to arrayOf("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"),
"cath" to listOf("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
"eve" to arrayOf("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"),
"dee" to listOf("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"),
"fay" to arrayOf("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"),
"eve" to listOf("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"),
"gay" to arrayOf("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"),
"fay" to listOf("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"),
"hope" to arrayOf("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"),
"gay" to listOf("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"),
"ivy" to arrayOf("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
"hope" to listOf("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"),
"jan" to arrayOf("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan")))
"ivy" to listOf("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
"jan" to listOf("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"))



with(EngagementRegistry(guys, girls)) {
fun buildPrefs(person: Person, stringPrefs: List<String>, population: List<Person>) {
print(this)
person.preferences.addAll(
analyse(guys, girls)
stringPrefs.map { name -> population.single { it.name == name } }
swap(girls, 0, 1)
analyse(guys, girls)
)
}
}

}</lang>
val males = inMales.keys.map { Person(it) }
val females = inFemales.keys.map { Person(it) }

males.forEach { buildPrefs(it, inMales[it.name]!!, females) }
females.forEach { buildPrefs(it, inFemales[it.name]!!, males) }


match(males)
males.forEach { println(it.showMatch()) }
println("#### match is stable: ${isStableMatch(males, females)}")


fun swapMatch(male1: Person, male2: Person) {
val female1 = male1.matchedTo!!
val female2 = male2.matchedTo!!

male1.matchedTo = female2
male2.matchedTo = female1

female1.matchedTo = male2
female2.matchedTo = male1
}

swapMatch(males.single { it.name == "fred" }, males.single { it.name == "jon" })
males.forEach { println(it.showMatch()) }
println("#### match is stable: ${isStableMatch(males, females)}")
}
</lang>
{{out}}
{{out}}
<pre>
See Java output.
abe <=> ivy
bob <=> cath
col <=> dee
dan <=> fay
ed <=> jan
fred <=> bea
gav <=> gay
hal <=> eve
ian <=> hope
jon <=> abi
##### match is stable: true
abe <=> ivy
bob <=> cath
col <=> dee
dan <=> fay
ed <=> jan
fred <=> abi
gav <=> gay
hal <=> eve
ian <=> hope
jon <=> bea
#### Unstable pair: fred <=> abi
##### match is stable: false
</pre>


=={{header|Lua}}==
=={{header|Lua}}==
Retrieved from "https://rosettacode.org/wiki/Stable_marriage_problem"