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>>) { |
|||
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> { |
|||
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 |
|||
} |
|||
} |
} |
||
} |
} |
||
fun prefers(p: Person) = when (matchedTo) { |
|||
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 |
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 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") |
|||
} |
} |
||
} |
|||
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 |
|||
} |
|||
} |
|||
if (!stable) { |
|||
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"), |
|||
" |
"abe" to mutableListOf("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"), |
||
" |
"bob" to mutableListOf("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"), |
||
" |
"col" to mutableListOf("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"), |
||
" |
"dan" to mutableListOf("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"), |
||
" |
"ed" to mutableListOf("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"), |
||
" |
"fred" to mutableListOf("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"), |
||
" |
"gav" to mutableListOf("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"), |
||
" |
"hal" to mutableListOf("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"), |
||
" |
"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"), |
|||
" |
"abi" to listOf("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"), |
||
" |
"bea" to listOf("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"), |
||
" |
"cath" to listOf("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"), |
||
" |
"dee" to listOf("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"), |
||
" |
"eve" to listOf("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"), |
||
" |
"fay" to listOf("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"), |
||
" |
"gay" to listOf("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"), |
||
" |
"hope" to listOf("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"), |
||
" |
"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) |
|||
) |
|||
} |
} |
||
}</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}}== |