C++ Program to Implement Stable Marriage Problem

This C++ Program demonstrates the implementation of the Stable Marriage Problem. Given N men and N women, where each person has ranked all members of the opposite gender in order of preference, marry the men and women together such that there are no two people of the opposite gender who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”.

Here is source code of the C++ Program to demonstrate the implementation of Stable Marriage Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  2.  * C++ Program to Implement Stable Marriage Problem
  3.  */
  4. #include <iostream>
  5. #include <string.h>
  6. #include <stdio.h>
  7. using namespace std;
  8.  
  9. // Number of Men or Women
  10. #define N  4
  11.  
  12. // This function returns true if woman 'w' prefers man 'm1' over man 'm'
  13. bool wPrefersM1OverM(int prefer[2*N][N], int w, int m, int m1)
  14. {
  15.     // Check if w prefers m over her current engagment m1
  16.     for (int i = 0; i < N; i++)
  17.     {
  18.  
  19.         // If m1 comes before m in the list of w, 
  20.         // then w prefers her current engagement, don't do anything
  21.  
  22.         if (prefer[w][i] == m1)
  23.             return true;
  24.  
  25.         // If m cmes before m1 in w's list, then free her current
  26.         // engagement and engage her with m
  27.         if (prefer[w][i] == m)
  28.            return false;
  29.     }
  30. }
  31.  
  32. // Prints stable matching for N boys and N girls. Boys are numbered as 0 to N-1.
  33. // Girls are numbered as N to 2N-1.
  34. void stableMarriage(int prefer[2*N][N])
  35. {
  36.     /*
  37.      Stores partner of women. This is our output array that stores information.
  38.      The value of wPartner[I] indicates the partner assigned to woman N+i.
  39.      Note that the woman numbers between N and 2*N-1. 
  40.      The value -1 indicates that (N+i)'th woman is free
  41.     */
  42.     int wPartner[N];
  43.  
  44.     // An array to store availability of men. If mFree[i] is false, 
  45.     // then man 'i' is free, otherwise engaged.
  46.     bool mFree[N];
  47.  
  48.     // Initialize all men and women as free
  49.     memset(wPartner, -1, sizeof(wPartner));
  50.     memset(mFree, false, sizeof(mFree));
  51.     int freeCount = N;
  52.  
  53.     // While there are free men
  54.     while (freeCount > 0)
  55.     {
  56.         // Pick the first free man (we could pick any)
  57.         int m;
  58.         for (m = 0; m < N; m++)
  59.             if (mFree[m] == false)
  60.                 break;
  61.  
  62.         // One by one go to all women according to m's preferences.
  63.         // Here m is the picked free man
  64.         for (int i = 0; i < N && mFree[m] == false; i++)
  65.         {
  66.             int w = prefer[m][i];
  67.  
  68.             // The woman of preference is free, w and m become partners.
  69.             // So we can say they are engaged not married
  70.             if (wPartner[w-N] == -1)
  71.             {
  72.                 wPartner[w-N] = m;
  73.                 mFree[m] = true;
  74.                 freeCount--;
  75.             }
  76.  
  77.             else  // If w is not free
  78.             {
  79.                 // Find current engagement of w
  80.                 int m1 = wPartner[w-N];
  81.  
  82.                 // If w prefers m over her current engagement m1,
  83.                 // then break the engagement between w and m1 and engage m with w.
  84.                 if (wPrefersM1OverM(prefer, w, m, m1) == false)
  85.                 {
  86.                     wPartner[w-N] = m;
  87.                     mFree[m] = true;
  88.                     mFree[m1] = false;
  89.                 }
  90.             }
  91.         } // End of the for loop that goes to all women in m's list
  92.     } // End of the main while loop
  93.  
  94.  
  95.     // Print the solution
  96.     cout << "Woman   Man" << endl;
  97.     for (int i = 0; i < N; i++)
  98.        cout << " " << i+N << "\t" << wPartner[i] << endl;
  99. }
  100.  
  101. // Driver program to test above functions
  102. int main()
  103. {
  104.     int prefer[2*N][N] = { {7, 5, 6, 4},
  105.         {5, 4, 6, 7},
  106.         {4, 5, 6, 7},
  107.         {4, 5, 6, 7},
  108.         {0, 1, 2, 3},
  109.         {0, 1, 2, 3},
  110.         {0, 1, 2, 3},
  111.         {0, 1, 2, 3},
  112.     };
  113.     stableMarriage(prefer);
  114.  
  115.     return 0;
  116. }

$ g++ stable_marriage.cpp
$ a.out
 
Woman   Man
 4      2
 5      1
 6      3
 7      0
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.