Stable marriage problem: Difference between revisions
Add Nim solution
SqrtNegInf (talk | contribs) m (→{{header|Sidef}}: Fix link: Perl 6 --> Raku) |
(Add Nim solution) |
||
Line 3,943:
Stable: false
</pre>
=={{header|Nim}}==
<lang 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)
</lang>
{{out}}
<pre>abe 💑 ivy
bob 💑 cath
col 💑 dee
dan 💑 fay
ed 💑 jan
fred 💑 bea
gav 💑 gay
hal 💑 eve
ian 💑 hope
jon 💑 abi
Current pair analysis:
✓ Stable
Swapping hal & abe partners
abe 💑 eve
bob 💑 cath
col 💑 dee
dan 💑 fay
ed 💑 jan
fred 💑 bea
gav 💑 gay
hal 💑 ivy
ian 💑 hope
jon 💑 abi
Current pair analysis:
💔 hal prefers eve over ivy
💔 eve prefers hal over abe
✗ Unstable</pre>
=={{header|Objective-C}}==
| |||