fork download
  1. //
  2. // main.cpp
  3. // Stable Matching Problem (Gale-Shapley algorithm)
  4. //
  5. // Created by Himanshu on 19/03/24.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <algorithm>
  11. #include <queue>
  12. using namespace std;
  13.  
  14. void printCurrentState (const vector<int> match, const vector<bool> engaged) {
  15.  
  16. int n = (int) match.size();
  17.  
  18. cout << endl << "Current matched pairs (w, m):" << endl;
  19. for (int i = 0; i < n; i++) {
  20. cout << "(" << i << ", " << match[i] << ")" << endl;
  21. }
  22.  
  23. cout << "Free men (m): " << endl;
  24. for (int i = 0; i < n; i++) {
  25. if (!engaged[i]) {
  26. cout << i << " ";
  27. }
  28. }
  29.  
  30. cout << endl;
  31.  
  32. }
  33.  
  34. vector<int> stableMarriage(const vector<vector<int>>& manPrefs, const vector<vector<int>>& womanPrefs) {
  35. int n = (int) manPrefs.size();
  36.  
  37. vector<int> match(n, -1); // Stores the matched man for each woman, -1 means unengaged
  38. vector<bool> engaged(n, false); // Indicates whether a man is engaged
  39.  
  40. // Queue to store the list of free men
  41. queue<int> freeMen;
  42. for (int i = 0; i < n; i++) freeMen.push(i);
  43.  
  44. while (!freeMen.empty()) {
  45.  
  46. int man = freeMen.front(); // Index of the unengaged man
  47. freeMen.pop();
  48.  
  49. // Find the best woman based on the man's preference list who has not rejected him
  50. for (int i = 0; i < n && !engaged[man]; i++) {
  51.  
  52. int woman = manPrefs[man][i]; // man's most preferred woman
  53.  
  54. // if the man's current preferred woman is unengaged
  55. if (match[woman] == -1) {
  56. match[woman] = man; // Engage the man to the woman
  57. engaged[man] = true;
  58.  
  59. printCurrentState(match, engaged);
  60. } else {
  61. int prevMatchedMan = match[woman];
  62.  
  63. //if woman prefer current "man" over previously matched man
  64. if (find(womanPrefs[woman].begin(), womanPrefs[woman].end(), man) < find(womanPrefs[woman].begin(), womanPrefs[woman].end(), prevMatchedMan)) {
  65.  
  66. match[woman] = man; // Engage the current man to the woman
  67. engaged[man] = true;
  68.  
  69. engaged[prevMatchedMan] = false; // Break the engagement with previous man
  70. freeMen.push(prevMatchedMan);
  71.  
  72. printCurrentState(match, engaged);
  73. }
  74. }
  75. }
  76. }
  77.  
  78. return match;
  79. }
  80.  
  81. int main() {
  82.  
  83. vector<vector<int>> menPrefs = {
  84. {1, 0, 2, 3},
  85. {3, 1, 0, 2},
  86. {0, 2, 1, 3},
  87. {1, 3, 2, 0}
  88. };
  89. vector<vector<int>> womenPrefs = {
  90. {0, 1, 2, 3},
  91. {1, 2, 3, 0},
  92. {2, 3, 0, 1},
  93. {3, 0, 1, 2}
  94. };
  95.  
  96. vector<int> pairs = stableMarriage(menPrefs, womenPrefs);
  97.  
  98. cout << "Stable pairings:" << endl;
  99. for (int i = 0; i < pairs.size(); i++) {
  100. cout << "Woman " << i << " is paired with Man " << pairs[i] << endl;
  101. }
  102.  
  103. return 0;
  104. }
  105.  
Success #stdin #stdout 0.01s 5304KB
stdin
Standard input is empty
stdout
Current matched pairs (w, m):
(0, -1)
(1, 0)
(2, -1)
(3, -1)
Free men (m): 
1 2 3 

Current matched pairs (w, m):
(0, -1)
(1, 0)
(2, -1)
(3, 1)
Free men (m): 
2 3 

Current matched pairs (w, m):
(0, 2)
(1, 0)
(2, -1)
(3, 1)
Free men (m): 
3 

Current matched pairs (w, m):
(0, 2)
(1, 3)
(2, -1)
(3, 1)
Free men (m): 
0 

Current matched pairs (w, m):
(0, 0)
(1, 3)
(2, -1)
(3, 1)
Free men (m): 
2 

Current matched pairs (w, m):
(0, 0)
(1, 3)
(2, 2)
(3, 1)
Free men (m): 

Stable pairings:
Woman 0 is paired with Man 0
Woman 1 is paired with Man 3
Woman 2 is paired with Man 2
Woman 3 is paired with Man 1