Stable matching matches least preferable

Question

I have implemented the stable matching algorithm but it seems that the implementation matches the least preferable candidates. I'm asking for a code review:

import options, sequtils

type
    Person* = ref object
        id: int
        name: string
        engagedTo: Option[Person]
        preferences: seq[Person]
    MatchPool* = object
        husbands, wives: seq[Person]

proc newPerson*(nameofperson: string, isMale: bool = true, engagedTo: Option[
        Person] = none(Person), preferences: openArray[Person] = []): Person =
    var
        nextMaleId = 1
        nextFemaleId = -1
        id: int
    if isMale:
        id = nextMaleId
        inc nextMaleId
    else:
        id = nextFemaleId
        dec nextFemaleId
    return Person(id: id, name: nameofperson, engagedTo: engagedTo,
            preferences: preferences.toSeq())

proc addPreference*(self: var Person, preference: varargs[Person]) =
    self.preferences.add(preference)

proc newMatchPool*(husbands, wives: openArray[Person]): Option[MatchPool] =
    let dim = husbands.len()
    if wives.len() == dim:
        if husbands.allIt(it.preferences.len() == dim):
            if wives.allIt(it.preferences.len() == dim):
                result = some(MatchPool(husbands: husbands.toSeq(),
                        wives: wives.toSeq()))

proc isSingle(self: Person): bool = self.engagedTo.isNone()

proc isEngaged(self: Person): bool = not self.isSingle()

proc disengage(person: var Person) =
    if person.engagedTo.isSome():
        person.engagedTo.get().engagedTo = none(Person)
    person.engagedTo = none(Person)

proc engage(husband, wife: var Person) =
    if husband.isEngaged():
        disengage(husband)
    if wife.isEngaged():
        disengage(wife)
    husband.engagedTo = some(wife)
    wife.engagedTo = some(husband)

proc prefersMoreThanCurrent(self, other: Person): Option[bool] =
    if self.isSingle():
        result = some(true)
    else:
        for personRef in self.preferences:
            if personRef.id == self.engagedTo.get().id:
                result = some(false)
                break
            elif personRef.id == other.id:
                result = some(true)
                break

proc solve*(self: var MatchPool): Option[string] =
    for husband in self.husbands.mitems():
        for wife in husband.preferences.mitems():
            let prefers = wife.prefersMoreThanCurrent(husband)
            if prefers.isNone():
                result = some("Found a spouse that does not prefer another spouse")
                break
            elif prefers.get():
                engage(husband, wife)
        result = none(string)

proc print*(self: MatchPool) =
    for husband in self.husbands:
        echo(husband.name, " is engaged to ", husband.engagedTo.get().name)
    echo "and"
    for wife in self.wives:
        echo(wife.name, " is engaged to ", wife.engagedTo.get().name)

driver:

import unittest
import options

import cdsan/stable_matching
test "stable_matching":
  var
    rose = newPerson("Rose", false)
    alexis = newPerson("Alexis", false)
    alicia = newPerson("Alicia", false)
    samantha = newPerson("Samantha", false)

    ads = newPerson("Ads")
    bruce = newPerson("Bruce")
    zab = newPerson("Zab")
    eddy = newPerson("Eddy")

  rose.addPreference(ads, zab, eddy, bruce)
  alexis.addPreference(bruce, zab, eddy, ads)
  alicia.addPreference(eddy, zab, bruce, ads)
  samantha.addPreference(bruce, eddy, zab, ads)

  ads.addPreference(rose, alicia, alexis, samantha)
  bruce.addPreference(samantha, alicia, rose, alexis)
  zab.addPreference(alexis, rose, alicia, samantha)
  eddy.addPreference(samantha, rose, alicia, alexis)

  var mp = newMatchPool(wives = [rose, alexis, alicia, samantha], husbands = [
      ads, bruce, zab, eddy])
  assert mp.isSome()
  var pool = mp.get()
  assert pool.solve().isNone()
  pool.print()

result:

Ads is engaged to Samantha
Bruce is engaged to Alexis
Zab is engaged to Alicia
Eddy is engaged to Rose
and
Rose is engaged to Eddy
Alexis is engaged to Bruce
Alicia is engaged to Zab
Samantha is engaged to Ads

As you can see, Ads and Samantha likes each others the least.Samantha likes Bruce.Rose and Ads prefer each other.

What's causing this?

Stable matching matches least preferable

Answers (1)

Related Questions