0

我已经实现了稳定匹配算法，但似乎该实现与最不受欢迎的候选者匹配。我要求进行代码审查：

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)

司机：

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()

结果：

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

如您所见，Ads 和 Samantha 最不喜欢对方。Samantha 喜欢 Bruce。Rose 和 Ads 更喜欢对方。

这是什么原因造成的？

4

1 回答 1

1

问题是，nextMaleId并且nextFemaleId是本地的newPerson。所以每个男性得到 id=1，每个女性得到 id=-1。

如果您制作全局变量并更改nextMaleId为仅在两个人都喜欢彼此而不是当前合作伙伴时才与他们互动，您会得到nextFemaleIdsolve

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

这看起来是一个可以接受的解决方案。

于 2020-04-25T09:50:07.043 回答