A Kotlin implementation of the Gale–Shapley algorithm for the stable marriage problem.

MarriageProblemSolver.kt

import MarriageProblemSolver.Person

class MarriageProblemSolver {
  class Person(val name: String) {
    internal lateinit var preferences: List<Person>
    internal var proposals = 0
    var match: Person? = null
      internal set

    // Do a lateinit to allow the circular dependency of people with their preferences of people.
    fun initializePreferences(preferences: List<Person>) {
      if (this::preferences.isInitialized) {
        throw IllegalStateException()
      }
      this.preferences = preferences
    }

    override fun toString() = name

    internal fun prefers(new: Person): Boolean {
      val old = match!!
      for (i in preferences.indices) {
        if (preferences[i] === new) {
          return true
        }
        if (preferences[i] === old) {
          return false
        }
      }
      throw NoSuchElementException()
    }
  }

  // Adds the matches to the Persons in the Collection.
  fun solve(men: Collection<Person>) {
    // Assume valid input.
    val freeMen = ArrayList(men)
    while (freeMen.isNotEmpty()) {
      // Take the last element because it is efficient to remove from the ArrayList.
      val freeMan = freeMen.last()
      val potentialMatch = freeMan.preferences[freeMan.proposals++]
      val oldMan = potentialMatch.match
      if (oldMan == null) {
        potentialMatch.match = freeMan
        freeMan.match = potentialMatch
        freeMen -= freeMan
      } else {
        if (potentialMatch.prefers(freeMan)) {
          oldMan.match = null
          potentialMatch.match = freeMan
          freeMan.match = potentialMatch
          freeMen += oldMan
          freeMen -= freeMan
        }
      }
    }
  }
}

private fun isStable(men: List<Person>): Boolean {
  for (i in men.indices) {
    val man = men[i]
    val woman = man.match!!
    var j = 0
    while (true) {
      val betterMan = woman.preferences[j++]
      if (betterMan === man) {
        break
      }
      val betterMansBetterWomen = betterMan.preferences
      var k = 0
      while (true) {
        val betterMansBetterWoman = betterMansBetterWomen[k++]
        if (betterMansBetterWoman === betterMan.match) {
          break
        }
        if (betterMansBetterWoman === woman) {
          return false
        }
      }
    }
  }
  return true
}

fun main() {
  val solver = MarriageProblemSolver()
  val number = 290
  val men = ArrayList<Person>(number).apply {
    for (i in 1..number) {
      add(Person("Man $i"))
    }
  }
  val women = ArrayList<Person>(number).apply {
    for (i in 1..number) {
      add(Person("Woman $i"))
    }
  }
  for (i in 0 until number) {
    men[i].initializePreferences(women.shuffled())
    women[i].initializePreferences(men.shuffled())
  }
  solver.solve(men)
  for (i in 0 until number) {
    val man = men[i]
    val woman = women[i]
    if (i != 0) {
      println()
    }
    println("${man}\nPrefers: ${man.preferences}\nMatched with: ${man.match!!}")
    println()
    println("${woman}\nPrefers: ${woman.preferences}\nMatched with: ${woman.match!!}")
  }
  println(isStable(men))
}