fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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
https://ideone.com/YsVEFF
language:
C++ 4.3.2 (gcc-4.3.2)
created:
99 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!