We will be writing program for Gale-Shapley Algorithm in C++. This algorithm is used to solve the Stable Marriage Problem.
You can get the problem on SPOJ,
or on codechef.
You can understand the algorithm from Gale-Shapley’s paper: College Admissions and the Stability of Marriage
The Algorithm
The algorithm is as follows:
1. set all men and women to be free.
2. while there is a man who is free.
2.1 select this free man m.
2.2 m proposes to the woman w which is at his highest preference and he has not proposed to her yet.
2.3 if w is free, then engage m and w.
2.4 else if w is engaged with someone who is she prefers less than w, then engage m and w and set w's previous partner to be free.
2.4 else w is engaged to someone who she prefers more than m, so let m remain free.
3. output the final engagements.Taking the input
So first, we will take our input. All the men are numbered from 1 to n. And all women are also numbered 1 to n. We will save the preference list as a 2d array for men(mList) and for women(wList).
mList[i][j] = k
means that ith man's jth preference is woman k
for example if mList[2][1] = 3, that means man 2 's 1st preference is woman 3.
And similarly for wList.
Since we are numbering man and woman from 1 to n, we will create our arrays of n+1 size, and not bother what is stored at index 0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#define SINGLE 0
int main() {
int t, n;
scanf("%d", &t); // number of test cases
while(t--) {
scanf("%d", &n);
int mList[n+1][n+1]; // men's preference list
int wList[n+1][n+1]; // women's preference list
int manCurrentMatch[n+1]; // current match of men
int womanCurrentMatch[n+1]; // current match of men
int manNextProposal[n+1]; // each man will propose this indexed woman in his preference list
//taking inputs...
for (int i = 1; i <= n; i++) { // for each woman
womanCurrentMatch[i] = SINGLE; // set her to be single
for(int j = 0; j <= n; j++) {
scanf("%d", &wList[i][j]);
}
}
for (int i = 1; i <= n; i++) { // for each man
manCurrentMatch[i] = SINGLE; // set him to be single
manNextProposal[i] = 1; // each man will start by proposing 1st woman in his list
for(int j = 0; j <= n; j++) {
scanf("%d", &mList[i][j]);
}
}
//algorithm...
//show output...
}
return 0;
}
Here manCurrentMatch is an array which stores the current engagement of every man, or set it to 0 if he is currently single.
manCurrentMatch[i] = kmeans that currently man i is engaged to woman k. Similarly we have womanCurrentMatch array.
While taking the input we are also setting the all the manCurrentMatch and womanCurrentMatch as SINGLE, which is defined to be 0(since there is no woman or man numbered 0).
manNextProposal is an array which tells that which indexed woman this man will propose next in his prefernce list.
manNextProposal[i] = kmeans that man i will propose woman mList[i][k] next.
So at the begining, every man will propose to their first choice, so manNextProposal[i] = 1 for every man i.
While Loop
Now, at each iteration of the while loop, we need to check if there is any free man available. Boolean freeManAvailable will be used for this purpose. At the very first iteration freeManAvailable will be true (because all men are free at the starting).
And at the end of each iteration, we will check again for a free man, if available then set freeManAvailable to true and take that free man into our variable m. At begining we set m = 1, i.e. we used man 1 as our first free man who will propose in first iteration of while loop.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
//algorithm...
bool freeManAvailable = true; // at begining we have free man available
int m = 1; // taking the first man as free for first iteration
while(freeManAvailable) {
freeManAvailable = false;
int w = mList[m][manNextProposal[m]++]; // the woman man proposes
if(womanCurrentMatch[w] == SINGLE) {
//w is currently free, engage (m and w)...
} else {
//w is engaged...
}
//finding a new free man...
for(int x = 1; x <= n; x++) {
if(manCurrentMatch[x] == SINGLE) {
m = x;
freeManAvailable = true;
break;
}
}
}
...
We can get the woman w, whom our man m will propose by:
w = mList[m][manNextProposal[m]++];Here we are also incrementing the manNextProposal[m], this means that he will propose his next preferenced woman(if such a condition arises at some later time).
We will first check if woman w is currently single, if she is, then engage m and w.
1
2
3
4
5
6
7
8
9
10
...
if(womanCurrentMatch[w] == SINGLE) {
//w is currently free, engage (m and w)...
womanCurrentMatch[w] = m;
manCurrentMatch[m] = w;
} else {
//w is engaged...
}
...
If woman w is not free, then we need to check if her current match is more prefered by her than m or not.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
if(womanCurrentMatch[w] == SINGLE) {
//w is currently free, engage (m and w)...
womanCurrentMatch[w] = m;
manCurrentMatch[m] = w;
} else {
//w is engaged...
bool itsABetterProposal = false; // check if it's a better proposal
//check her preference list
for(int y = 1; y <= n; y++) {
if(wList[w][y] == womanCurrentMatch[w]) {
itsABetterProposal = false; break;
}
if(wList[w][y] == m) {
itsABetterProposal = true; break;
}
}
if(itsABetterProposal) {
// if a better proposal, then engage (m and w), and set w's previous partner as free...
manCurrentMatch[womanCurrentMatch[w]] = SINGLE;
womanCurrentMatch[w] = m;
manCurrentMatch[m] = w;
}
}
...
Finally we will show the output as mentioned in the problem statement. And here is the final code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#define SINGLE 0
int main() {
int t, n;
scanf("%d", &t); // number of test cases
while(t--) {
scanf("%d", &n);
int mList[n+1][n+1]; // men's preference list
int wList[n+1][n+1]; // women's preference list
int manCurrentMatch[n+1]; // current match of men
int womanCurrentMatch[n+1]; // current match of men
int manNextProposal[n+1]; // each man will propose this indexed woman in his preference list
//taking inputs...
for (int i = 1; i <= n; i++) { // for each woman
womanCurrentMatch[i] = SINGLE; // set her to be single
for(int j = 0; j <= n; j++) {
scanf("%d", &wList[i][j]);
}
}
for (int i = 1; i <= n; i++) { // for each man
manCurrentMatch[i] = SINGLE; // set him to be single
manNextProposal[i] = 1; // each man will start by proposing 1st woman in his list
for(int j = 0; j <= n; j++) {
scanf("%d", &mList[i][j]);
}
}
//algorithm...
bool freeManAvailable = true; // at begining we have free man available
int m = 1; // taking the first man as free for first iteration
while(freeManAvailable) {
freeManAvailable = false;
int w = mList[m][manNextProposal[m]++]; // the woman man proposes
if(womanCurrentMatch[w] == SINGLE) {
//w is currently free, engage (m and w)...
womanCurrentMatch[w] = m;
manCurrentMatch[m] = w;
} else {
//w is engaged...
bool itsABetterProposal = false; // check if it's a better proposal
//check her preference list
for(int y = 1; y <= n; y++) {
if(wList[w][y] == womanCurrentMatch[w]) {
itsABetterProposal = false; break;
}
if(wList[w][y] == m) {
itsABetterProposal = true; break;
}
}
if(itsABetterProposal) {
// if a better proposal, then engage (m and w), and set w's previous partner as free...
manCurrentMatch[womanCurrentMatch[w]] = SINGLE;
womanCurrentMatch[w] = m;
manCurrentMatch[m] = w;
}
}
//finding a new free man...
for(int x = 1; x <= n; x++) {
if(manCurrentMatch[x] == SINGLE) {
m = x;
freeManAvailable = true;
break;
}
}
}
//show output...
for(int i = 1; i <= n; i++) {
printf("%d %d\n", i, manCurrentMatch[i]);
}
}
return 0;
}