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.
/*
* C++ Program to Implement Stable Marriage Problem
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
// Number of Men or Women
#define N 4
// This function returns true if woman 'w' prefers man 'm1' over man 'm'
bool wPrefersM1OverM(int prefer[2*N][N], int w, int m, int m1)
{
// Check if w prefers m over her current engagment m1
for (int i = 0; i < N; i++)
{
// If m1 comes before m in the list of w,
// then w prefers her current engagement, don't do anything
if (prefer[w][i] == m1)
return true;
// If m cmes before m1 in w's list, then free her current
// engagement and engage her with m
if (prefer[w][i] == m)
return false;
}
}
// Prints stable matching for N boys and N girls. Boys are numbered as 0 to N-1.
// Girls are numbered as N to 2N-1.
void stableMarriage(int prefer[2*N][N])
{
/*
Stores partner of women. This is our output array that stores information.
The value of wPartner[I] indicates the partner assigned to woman N+i.
Note that the woman numbers between N and 2*N-1.
The value -1 indicates that (N+i)'th woman is free
*/
int wPartner[N];
// An array to store availability of men. If mFree[i] is false,
// then man 'i' is free, otherwise engaged.
bool mFree[N];
// Initialize all men and women as free
memset(wPartner, -1, sizeof(wPartner));
memset(mFree, false, sizeof(mFree));
int freeCount = N;
// While there are free men
while (freeCount > 0)
{
// Pick the first free man (we could pick any)
int m;
for (m = 0; m < N; m++)
if (mFree[m] == false)
break;
// One by one go to all women according to m's preferences.
// Here m is the picked free man
for (int i = 0; i < N && mFree[m] == false; i++)
{
int w = prefer[m][i];
// The woman of preference is free, w and m become partners.
// So we can say they are engaged not married
if (wPartner[w-N] == -1)
{
wPartner[w-N] = m;
mFree[m] = true;
freeCount--;
}
else // If w is not free
{
// Find current engagement of w
int m1 = wPartner[w-N];
// If w prefers m over her current engagement m1,
// then break the engagement between w and m1 and engage m with w.
if (wPrefersM1OverM(prefer, w, m, m1) == false)
{
wPartner[w-N] = m;
mFree[m] = true;
mFree[m1] = false;
}
}
} // End of the for loop that goes to all women in m's list
} // End of the main while loop
// Print the solution
cout << "Woman Man" << endl;
for (int i = 0; i < N; i++)
cout << " " << i+N << "\t" << wPartner[i] << endl;
}
// Driver program to test above functions
int main()
{
int prefer[2*N][N] = { {7, 5, 6, 4},
{5, 4, 6, 7},
{4, 5, 6, 7},
{4, 5, 6, 7},
{0, 1, 2, 3},
{0, 1, 2, 3},
{0, 1, 2, 3},
{0, 1, 2, 3},
};
stableMarriage(prefer);
return 0;
}
$ 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]Related Posts:
- Check Computer Science Books
- Check C++ Books
- Practice Programming MCQs
- Check Programming Books
- Apply for Computer Science Internship