Стабильное соответствие наименее предпочтительным - PullRequest
Новая
       44

Стабильное соответствие наименее предпочтительным

0 голосов
/ 08 марта 2020

Я реализовал алгоритм стабильного сопоставления, но кажется, что реализация соответствует наименее предпочтительным кандидатам. Я прошу пересмотреть код: 

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 and Samantha нравится каждому другие меньше всего. Саманте нравится Брюс. Розы и реклама предпочитают друг друга.

Что вызывает это?

1 Ответ

0 голосов
/ 25 апреля 2020

Проблема в том, что nextMaleId и nextFemaleId являются локальными для newPerson. Таким образом, каждый мужчина получает id = 1, а каждая женщина получает id = -1.

Если вы зададите глобальные переменные nextMaleId и nextFemaleId и измените solve, чтобы задействовать только двух человек, если они оба предпочитают друг друга через своего нынешнего партнера вы получаете 

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

, что выглядит как приемлемое решение.

...