117 lines
5.2 KiB
Nim
117 lines
5.2 KiB
Nim
import sequtils, random, strutils
|
|
|
|
const
|
|
Pairs = 10
|
|
MNames = ["abe", "bob", "col", "dan", "ed", "fred", "gav", "hal", "ian", "jon"]
|
|
FNames = ["abi", "bea", "cath", "dee", "eve", "fay", "gay", "hope", "ivy", "jan"]
|
|
MPreferences = [
|
|
["abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"],
|
|
["cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"],
|
|
["hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"],
|
|
["ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"],
|
|
["jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"],
|
|
["bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"],
|
|
["gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"],
|
|
["abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"],
|
|
["hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"],
|
|
["abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"]
|
|
]
|
|
FPreferences = [
|
|
["bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"],
|
|
["bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"],
|
|
["fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"],
|
|
["fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"],
|
|
["jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"],
|
|
["bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"],
|
|
["jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"],
|
|
["gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"],
|
|
["ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"],
|
|
["ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"]
|
|
]
|
|
|
|
# recipient's preferences hold the preference score for each contender's id
|
|
func getRecPreferences[N: static int](prefs: array[N, array[N, string]],
|
|
names: openArray[string]): array[N, array[N, int]] {.compileTime.} =
|
|
for r, prefArray in pairs(prefs):
|
|
for c, contender in pairs(prefArray):
|
|
result[r][c] = prefArray.find(MNames[c])
|
|
|
|
# contender's preferences hold the recipient ids in descending order of preference
|
|
func getContPreferences[N: static int](prefs: array[N, array[N, string]],
|
|
names: openArray[string]): array[N, array[N, int]] {.compileTime.} =
|
|
for c, pref_seq in pairs(prefs):
|
|
for r, pref in pairs(pref_seq):
|
|
result[c][r] = names.find(pref)
|
|
|
|
const
|
|
RecipientPrefs = getRecPreferences(FPreferences, MNames)
|
|
ContenderPrefs = getContPreferences(MPreferences, FNames)
|
|
|
|
proc printCoupleNames(contPairs: seq[int]) =
|
|
for c, r in pairs(contPairs):
|
|
echo MNames[c] & " 💑 " & FNames[contPairs[c]]
|
|
|
|
func pair(): (seq[int], seq[int]) =
|
|
# double booking to avoid inverse lookup using find
|
|
var
|
|
recPairs = newSeqWith(10, -1)
|
|
contPairs = newSeqWith(10, -1)
|
|
template engage(c, r: int) =
|
|
#echo FNames[r] & " accepted " & MNames[c]
|
|
contPairs[c] = r
|
|
recPairs[r] = c
|
|
var contQueue = newSeqWith(10, 0)
|
|
while contPairs.contains(-1):
|
|
for c in 0..<Pairs:
|
|
if contPairs[c] == -1:
|
|
let r = ContenderPrefs[c][contQueue[c]] #proposing to first in queue
|
|
contQueue[c] += 1 #increment contender's queue for following iterations
|
|
let curPair = recPairs[r] # current pair's index or -1 = vacant
|
|
if curPair == -1:
|
|
engage(c, r)
|
|
# contender is more preferable than current
|
|
elif RecipientPrefs[r][c] < RecipientPrefs[r][curPair]:
|
|
contPairs[curPair] = -1 # vacate current pair
|
|
#echo MNames[curPair] & " was dumped by " & FNames[r]
|
|
engage(c, r)
|
|
result = (contPairs, recPairs)
|
|
|
|
proc randomPair(max: int): (int, int) =
|
|
let a = rand(max)
|
|
var b = rand(max - 1)
|
|
if b == a:
|
|
b = max
|
|
result = (a, b)
|
|
|
|
proc perturbPairs(contPairs, recPairs: var seq[int]) =
|
|
randomize()
|
|
let (a, b) = randomPair(Pairs-1)
|
|
echo("Swapping ", MNames[a], " & ", MNames[b], " partners")
|
|
swap(contPairs[a], contPairs[b])
|
|
swap(recPairs[contPairs[a]], recPairs[contPairs[b]])
|
|
|
|
proc checkPairStability(contPairs, recPairs: seq[int]): bool =
|
|
for c in 0..<Pairs: # each contender
|
|
let curPairScore = ContenderPrefs[c].find(contPairs[c]) # pref. score for current pair
|
|
for preferredRec in 0..<curPairScore: # try every recipient with higher score
|
|
let
|
|
checkedRec = ContenderPrefs[c][preferredRec]
|
|
curRecPair = recPairs[checkedRec] # current pair of checked recipient
|
|
# if score of the curRecPair is worse (>) than score of checked contender
|
|
if RecipientPrefs[checkedRec][curRecPair] > RecipientPrefs[checkedRec][c]:
|
|
echo("💔 ", MNames[c], " prefers ", FNames[checkedRec], " over ", FNames[contPairs[c]])
|
|
echo("💔 ", FNames[checkedRec], " prefers ", MNames[c], " over ", MNames[curRecPair])
|
|
echo "✗ Unstable"
|
|
return false # unstable
|
|
echo "✓ Stable"
|
|
result = true
|
|
|
|
when isMainModule:
|
|
var (contPairs, recPairs) = pair()
|
|
printCoupleNames(contPairs)
|
|
echo "Current pair analysis:"
|
|
discard checkPairStability(contPairs, recPairs)
|
|
perturbPairs(contPairs, recPairs)
|
|
printCoupleNames(contPairs)
|
|
echo "Current pair analysis:"
|
|
discard checkPairStability(contPairs, recPairs)
|