# 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)

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