Stable marriage problem: Difference between revisions
Content added Content deleted
m (Moved Bracmat below BBC Basic) |
m (added whitespace before the TOC (table of contents), added other whitespace before task preamble headers.) |
||
| Line 1: | Line 1: | ||
{{task|Classic CS problems and programs}} |
{{task|Classic CS problems and programs}} |
||
Solve the [[wp:Stable marriage problem|Stable marriage problem]] using the Gale/Shapley algorithm. |
Solve the [[wp:Stable marriage problem|Stable marriage problem]] using the Gale/Shapley algorithm. |
||
'''Problem description'''<br> |
'''Problem description'''<br> |
||
| Line 8: | Line 9: | ||
Gale and Shapley proved that there is a stable set of engagements for any set of preferences and the first link above gives their algorithm for finding a set of stable engagements. |
Gale and Shapley proved that there is a stable set of engagements for any set of preferences and the first link above gives their algorithm for finding a set of stable engagements. |
||
'''Task Specifics'''<br> |
'''Task Specifics'''<br> |
||
| Line 40: | Line 42: | ||
# Use the Gale Shapley algorithm to find a stable set of engagements |
# Use the Gale Shapley algorithm to find a stable set of engagements |
||
# Perturb this set of engagements to form an unstable set of engagements then check this new set for stability. |
# Perturb this set of engagements to form an unstable set of engagements then check this new set for stability. |
||
'''References''' |
'''References''' |
||
| Line 48: | Line 51: | ||
# [https://www.youtube.com/watch?v=LtTV6rIxhdo Stable Marriage Problem (the math bit)] (Video). |
# [https://www.youtube.com/watch?v=LtTV6rIxhdo Stable Marriage Problem (the math bit)] (Video). |
||
# [http://www.ams.org/samplings/feature-column/fc-2015-03 The Stable Marriage Problem and School Choice]. (Excellent exposition) |
# [http://www.ams.org/samplings/feature-column/fc-2015-03 The Stable Marriage Problem and School Choice]. (Excellent exposition) |
||
<br><br> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||