Stable marriage problem: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Sidef}}: Fix link: Perl 6 --> Raku) |
(Add Nim solution) |
||
Line 3,943: | Line 3,943: | ||
Stable: false |
Stable: false |
||
</pre> |
</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}}== |
=={{header|Objective-C}}== |