Stable Roommates
The stable roommates problem involves a single set of even cardinality n, each member of which ranks all the others in order of preference. A stable matching is now a partition of this single set into n^2 pairs so that no two unmatched members both prefer each other to their partners under the matching. In this case, there are problem instances for which no stable matching exists. However, Irving's paper describes an O(n^2) algorithm that will determine, for any instance of the problem, whether a stable matching exists, and if so, will find that matching.
Demo
Set A (only single set needed for the SR problem)
| Caleb | ['Sadab', 'Ryan', 'Alex', 'Luis', 'Yoomin', 'Amber', 'May'] |
|---|---|
| May | ['Yoomin', 'Sadab', 'Ryan', 'Alex', 'Luis', 'Amber', 'Caleb'] |
| Luis | ['Yoomin', 'Sadab', 'Ryan', 'Alex', 'Caleb', 'Amber', 'May'] |
| Sadab | ['Ryan', 'Alex', 'Luis', 'Caleb', 'Yoomin', 'Amber', 'May'] |
| Ryan | ['Alex', 'Luis', 'Caleb', 'Amber', 'Yoomin', 'Sadab', 'May'] |
| Alex | ['May', 'Yoomin', 'Sadab', 'Ryan', 'Luis', 'Amber', 'Caleb'] |
| Yoomin | ['Sadab', 'Ryan', 'Alex', 'Luis', 'Caleb', 'Amber', 'May'] |
| Amber | ['Ryan', 'Alex', 'Luis', 'Caleb', 'Yoomin', 'Sadab', 'May'] |
Results
| Caleb matched with Sadab |
| May matched with Alex |
| Luis matched with Yoomin |
| Sadab matched with Caleb |
| Ryan matched with Amber |
| Alex matched with May |
| Yoomin matched with Luis |
| Amber matched with Ryan |
Try it yourself!
[*] Robert W. Irving, "An efficient algorithm for the “stable roommates” problem", Journal of Algorithms, Volume 6, Issue 4, 1985, Pages 577-595