Chapter 11, p. 738, Programming Project #2 \"Stable Marriage\" Program PLEASE HE
ID: 673443 • Letter: C
Question
Chapter 11, p. 738, Programming Project #2 "Stable Marriage" Program PLEASE HELP Programming Assignment This program will give you practice with a complex data structure. You are going to write a program that solves a classic computer science problem known as the stable marriage problem. The input file is divided into men and women and the program tries to pair them up so as to generate as many marriages as possible that are all stable. A set of marriages is unstable if you can find a man and a woman who would rather be married to each other than to their spouses (in which case, the two would be inclined to divorce their spouses and marry each other). The input file for the program will list all of the men, one per line, followed by an input line with just the word “END” on it, followed by all of the women, one per line, followed by another input line with just the word “END” on it. The men and women are numbered by their position in the input file. To make this easier, we have numbered starting at 0 (the first man is #0, the second man is #1, and so on; the first woman is #0, the second woman is #1, and so on). Each input line (except the two lines with “END”) has a name followed by a colon followed by a list of integers. The integers are the preferences for this particular person. For example, the following input line in the men's section: Joe: 9 7 34 8 19 21 32 5 28 6 31 15 17 24 indicates that the person is named “Joe” and that his first choice for marriage is woman #9, his second choice is woman #7, and so on. Any women not listed are considered unacceptable to Joe. The data file has been purged of any impossible pairings where one person is interested in the other, but the other considers that person unacceptable. Thus, if a woman appears on Joe’s list, then Joe is acceptable to that woman. There are many ways to approach the stable marriage problem. You are to implement a specific algorithm described below. This is the basic outline: set each person to be free; while (some man m with a nonempty preference list is free) { w = first woman on m's list; if (some man p is engaged to w) { set p to be free } set m and w to be engaged to each other for (each successor q of m on w's list) { delete w from q's preference list delete q from w's preference list } } Consider, for example, the following short input: Man 0: 3 0 1 2 Woman 0: 3 0 2 1 Man 1: 1 2 0 3 Woman 1: 0 2 1 3 Man 2: 1 3 2 0 Woman 2: 0 1 2 3 Man 3: 2 0 3 1 Woman 3: 3 0 2 1 It doesn't matter where we start, so suppose we start with man 0. We engage him to woman 3 (the first choice on his list). Men 2 and 1 appear after man 0 in woman 3's list. Thus, we delete those connections. Man 0: 3 0 1 2 Woman 0: 3 0 2 1 Man 0 and Woman 3 engaged Man 1: 1 2 0 Woman 1: 0 2 1 3 Man 2: 1 2 0 Woman 2: 0 1 2 3 Man 3: 2 0 3 1 Woman 3: 3 0 Notice that three things have changed: the list for man 1, the list for man 2 and the list for woman 3. Suppose we next go to man 1. We engage him to woman 1. Man 3 appears after man 1 on woman 1's list, so we have to delete that connection, obtaining: Man 0: 3 0 1 2 Woman 0: 3 0 2 1 Man 0 and Woman 3 engaged Man 1: 1 2 0 Woman 1: 0 2 1 Man 1 and Woman 1 engaged Man 2: 1 2 0 Woman 2: 0 1 2 3 Man 3: 2 0 3 Woman 3: 3 0 Notice that two things have changed: the list for man 3 and the list for woman 1. Suppose we next go to man 2. We engage him to woman 1, which requires breaking woman 1's engagement to man 1 (making man 1 again available). Man 1 appears after man 2 on woman 1's list, so we break that connection, obtaining: Man 0: 3 0 1 2 Woman 0: 3 0 2 1 Man 0 and Woman 3 engaged Man 1: 2 0 Woman 1: 0 2 Man 2: 1 2 0 Woman 2: 0 1 2 3 Man 2 and Woman 1 engaged Man 3: 2 0 3 Woman 3: 3 0 Suppose we next go to man 3. We engage him to woman 2. Nobody appears on woman 2's list after man 3, so we don't have to remove any connections: Man 0: 3 0 1 2 Woman 0: 3 0 2 1 Man 0 and Woman 3 engaged Man 1: 2 0 Woman 1: 0 2 Man 2: 1 2 0 Woman 2: 0 1 2 3 Man 2 and Woman 1 engaged Man 3: 2 0 3 Woman 3: 3 0 Man 3 and Woman 2 engaged Now we go back to man 1 (because he's still free). We engage him to woman 2, which requires breaking woman 2's engagement to man 3 (making man 3 again available). Men 2 and 3 appear after man 1 on woman 2's list, so we break those connections, obtaining: Man 0: 3 0 1 2 Woman 0: 3 0 2 1 Man 0 and Woman 3 engaged Man 1: 2 0 Woman 1: 0 2 Man 1 and Woman 2 engaged Man 2: 1 0 Woman 2: 0 1 Man 2 and Woman 1 engaged Man 3: 0 3 Woman 3: 3 0 Finally, the last free man is man 3. We engage him to woman 0. We could actually stop at this point, but according to the algorithm, we should notice that men 0, 2 and 1 all appear after man 3 on woman 0's list, so we break those connections: Man 0: 3 1 2 Woman 0: 3 Man 0 and Woman 3 engaged Man 1: 2 Woman 1: 0 2 Man 1 and Woman 2 engaged Man 2: 1 Woman 2: 0 1 Man 2 and Woman 1 engaged Man 3: 0 3 Woman 3: 3 0 Man 3 and Woman 0 engaged This, then, is our stable marriage solution. An interesting property of this simple stable marriage algorithm is that it favors one group over the other. The approach above favors the men at the expense of the women. In fact, the final result will give each man his best possible match for stable marriage situations, and will give each woman her worst possible match. But there is no reason that the algorithm can't be reversed with the women being favored over the men (just reversing the roles in the algorithm above). You will also report in a column called “Choice” the relative position of the chosen partner in the original preference list and you will report the average of the choice column at the end of each sublist. For example, you will find the following line of output for the result that favors the men: Name Choice Partner -------------------------------------- William 6 Rachana This indicates that William is paired with Rachana, and that Rachana was 6th on William's original list. The result that favors the women has this line of output: Name Choice Partner -------------------------------------- William 19 Caroline This indicates that William is paired with Caroline, and that Caroline was 19th on William's original list. The stable marriage algorithm always converges on an answer, but it is possible that some people will end up without being paired (this is inevitable in the large sample input file where there are 40 men and 35 women). Remember that the original algorithm terminates when there are no men left who are free and have a nonempty preference list. People are unpaired in the final result if they run out of choices on their preference lists. Be careful not to report a “choice” value for these people and don't include them in the calculation of the overall choice value. HERE ARE THE FILES TO HELP USE TO MAKE IT RUN: 1)PERSON.JAVA : import java.util.*; public class Person { public static final int NOBODY = -1; private String name; private List preferences; private List oldPreferences; private int partner; public Person(String name) { this.name = name; preferences = new ArrayList(); oldPreferences = new ArrayList(); erasePartner(); } public void erasePartner() { partner = NOBODY; } public boolean hasPartner() { return partner != NOBODY; } public int getPartner() { return partner; } public void setPartner(int partner) { this.partner = partner; } public String getName() { return name; } public boolean hasChoices() { return !preferences.isEmpty(); } public int getFirstChoice() { return preferences.get(0); } public void addChoice(int person) { preferences.add(person); oldPreferences.add(person); } public List getChoices() { return preferences; } public int getPartnerRank() { return oldPreferences.indexOf(partner) + 1; } } 2)SHORT.DAT : Man 0: 3 0 1 2 Man 1: 1 2 0 3 Man 2: 1 3 2 0 Man 3: 2 0 3 1 END Woman 0: 3 0 2 1 Woman 1: 0 2 1 3 Woman 2: 0 1 2 3 Woman 3: 3 0 2 1 END 3) STABLE.DAT : Joe: 9 7 34 8 19 21 32 5 28 6 31 15 17 24 Kevin: 23 25 11 27 8 5 10 0 17 33 30 32 19 13 16 7 18 31 9 12 34 22 1 Arnold: 1 0 12 19 26 27 11 10 17 21 34 29 15 4 14 5 33 22 8 30 28 Herbert: 2 8 5 31 15 20 25 34 9 29 0 David: 31 23 33 14 22 32 12 11 26 8 21 24 25 34 2 18 27 15 19 1 6 0 17 10 Brett: 17 0 15 6 27 21 10 2 20 14 22 3 7 31 13 8 19 4 32 24 9 5 33 18 28 25 12 1 11 30 16 23 34 26 29 Arun: 21 5 34 15 1 12 31 17 28 0 16 Andres: 5 32 22 26 0 4 27 12 9 6 3 15 29 33 7 34 8 30 16 14 11 24 10 13 19 23 1 John: 9 0 18 1 21 20 3 29 24 14 Ted: 18 0 21 29 32 14 26 19 10 24 31 23 1 16 22 11 9 7 5 12 20 Craig: 27 33 8 6 7 21 4 16 26 13 12 Matthew: 26 33 24 22 27 34 7 1 8 21 14 10 3 11 0 4 16 13 32 2 23 20 25 31 19 15 12 28 5 6 30 29 9 18 17 Seth: 13 24 2 18 17 9 31 26 15 14 4 27 22 0 20 33 29 32 28 16 19 30 Cliff: 8 6 13 11 9 3 19 28 33 32 2 34 23 Adrian: 32 9 23 24 1 4 27 11 5 8 12 16 34 17 31 29 3 25 13 30 2 15 22 19 14 0 6 William: 21 24 11 32 4 17 18 16 26 33 22 9 27 0 25 15 8 2 23 10 Martin: 2 6 20 11 7 17 29 24 23 9 3 13 22 12 1 Brian: 6 27 22 25 29 0 3 33 34 32 8 30 28 18 11 23 13 15 19 7 12 9 5 17 Edward: 10 4 12 34 22 0 19 20 5 11 24 16 21 13 7 3 15 28 6 8 25 9 2 1 33 30 31 18 Scott: 22 11 31 7 2 17 18 19 15 26 28 5 30 13 8 32 Sean: 21 7 6 31 33 34 0 16 14 32 17 22 Kirk: 24 5 32 20 28 2 10 27 4 9 30 1 21 7 14 16 29 Norman: 16 19 9 5 29 12 11 23 27 28 32 6 13 26 21 20 30 22 31 1 8 2 15 10 7 18 24 0 25 17 33 Michael: 18 1 4 34 7 12 28 32 16 0 22 Jason: 1 16 2 8 28 32 24 26 25 31 Tom: 22 25 17 16 30 0 21 34 4 27 13 10 20 11 Patrick: 34 33 13 26 21 22 14 10 32 8 1 15 3 29 18 20 2 4 17 30 7 19 28 12 23 24 0 11 31 27 25 Mark: 4 24 25 10 0 21 14 9 12 33 20 16 22 15 32 31 7 3 27 11 34 8 26 23 18 17 29 Gil: 24 9 14 23 1 27 33 12 3 4 Jeff: 10 33 16 29 34 1 3 31 21 0 17 13 27 8 6 24 4 30 18 11 5 32 22 Rich: 30 9 18 8 14 1 7 27 12 0 11 32 33 26 21 5 22 24 4 17 15 19 Derrick: 18 4 24 33 21 3 1 26 29 7 15 11 28 8 19 27 12 Curtis: 18 22 10 26 33 27 7 5 9 17 29 32 19 20 1 16 21 25 30 2 14 15 31 24 8 4 23 34 Eric: 31 26 2 11 0 16 12 8 19 24 17 21 27 6 5 22 14 10 30 13 28 20 7 25 33 23 29 3 9 Nick: 2 32 20 9 26 17 10 24 8 15 29 31 13 22 28 23 34 14 4 1 21 27 7 30 16 5 0 3 11 33 25 12 Ramon: 22 4 7 33 34 2 27 28 21 12 14 26 25 10 5 18 16 13 19 9 30 23 32 3 6 Robert: 23 24 30 6 21 11 29 16 34 9 31 26 14 19 3 22 20 18 7 1 17 25 10 8 Charles: 16 26 2 10 30 32 21 3 9 11 19 33 4 20 1 13 25 34 29 31 17 12 24 0 18 Steve: 19 33 7 17 20 13 24 30 2 15 25 1 11 28 8 0 14 22 29 27 10 18 26 23 Carlos: 20 11 7 15 16 12 13 2 31 3 19 17 6 5 28 9 END Jane: 17 3 14 18 12 38 6 26 22 25 30 33 1 2 20 9 11 37 8 27 7 29 15 4 5 34 23 Mary-Anne: 23 18 22 11 29 1 5 7 36 28 21 37 30 4 6 32 31 2 38 8 24 16 9 34 26 14 Elizabeth: 38 21 4 24 22 39 13 11 15 34 33 37 5 3 18 19 26 32 16 12 14 35 Eleanor: 8 14 37 36 29 35 33 28 26 5 7 31 17 18 16 39 13 34 27 11 Trudy: 37 32 10 2 23 30 11 14 12 34 7 29 15 21 18 5 25 26 31 27 28 35 Maria: 21 7 0 1 18 22 33 34 11 29 17 2 30 5 32 6 9 39 35 14 19 3 Helena: 35 16 14 13 0 5 11 20 18 22 17 36 33 39 29 4 10 7 Crystal: 10 34 21 26 23 30 11 0 19 31 5 35 18 38 17 36 27 16 20 22 39 32 33 1 9 7 Susan: 2 33 1 24 15 4 10 14 19 29 0 22 36 5 13 32 30 27 7 38 18 11 34 31 17 26 3 Robyn: 35 16 3 11 12 22 17 36 15 27 14 30 39 7 18 8 0 9 5 13 32 34 28 1 37 21 33 Moon-Star: 11 9 1 7 18 35 32 21 4 38 34 37 26 27 29 15 25 22 33 2 5 36 Debbie: 17 5 7 11 19 2 13 33 26 22 30 27 29 39 34 14 38 16 4 18 37 15 25 1 9 31 36 Nichole: 16 14 2 22 28 7 6 26 11 33 1 5 35 27 17 23 10 4 31 18 37 34 39 9 30 Jennifer: 16 5 18 11 14 35 29 1 26 7 13 12 17 33 10 19 37 25 38 22 34 39 Stephanie: 11 27 20 12 9 26 32 30 36 35 21 4 28 33 38 34 2 14 8 7 5 Mary: 3 2 4 5 7 30 11 15 38 17 14 6 32 12 22 18 34 0 39 19 26 27 31 Tara: 1 33 15 32 20 34 9 36 22 23 27 25 6 39 11 7 24 21 29 18 14 12 35 5 37 10 Rachana: 29 1 2 34 15 12 19 37 14 22 5 17 6 11 0 30 25 38 33 32 39 20 16 36 27 4 26 Farah: 5 4 18 37 11 8 26 9 23 19 32 35 27 22 17 12 30 29 36 31 1 38 15 Yvette: 2 4 1 19 14 13 17 30 18 37 5 12 7 9 32 36 35 11 0 31 26 22 33 38 39 Anna: 27 5 9 16 21 18 32 39 34 22 3 25 38 36 11 8 26 12 33 37 Irene: 34 2 5 10 33 9 36 0 15 31 32 27 8 20 30 21 22 25 29 26 35 37 18 4 6 11 Sylvia: 36 11 23 9 12 16 7 5 33 4 38 34 19 27 30 17 1 20 35 15 25 18 14 2 22 26 29 32 Caroline: 38 26 15 28 16 11 17 9 27 22 35 7 14 5 33 36 1 32 34 13 4 Wendy: 5 36 34 12 27 22 32 18 15 21 7 31 9 8 26 4 14 11 38 33 24 28 37 30 16 29 0 Marla: 34 25 14 36 37 32 18 26 1 33 27 35 15 3 17 38 4 5 11 22 24 Kim: 22 10 35 15 37 38 33 7 26 31 34 27 24 36 2 32 9 30 5 4 19 12 11 Angie: 30 12 5 15 29 25 10 22 2 17 4 34 32 21 27 7 31 26 11 1 14 38 35 33 28 Tessa: 22 39 33 26 5 17 23 34 35 38 21 12 24 0 2 31 19 13 18 6 11 Althea: 17 11 14 22 26 9 2 3 29 36 7 31 12 34 5 27 8 38 37 33 21 32 16 Lucy: 26 30 37 38 19 17 14 22 11 25 7 29 32 34 1 5 33 18 12 36 21 35 2 Julie: 27 39 4 5 11 22 18 19 26 34 20 36 14 33 1 32 0 37 29 12 9 24 3 6 Jean: 34 11 14 21 22 7 19 29 30 35 37 9 20 23 27 5 13 26 1 0 24 17 32 15 12 4 Maude: 5 28 29 1 15 37 13 20 30 27 11 38 17 26 31 22 35 18 7 33 34 32 2 10 4 12 Mary-Beth: 3 27 0 36 14 18 17 34 20 5 35 1 26 6 32 37 7 4 29 23 2 25 13 11 END
Explanation / Answer
Given N men and N women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable” (Source Wiki).
Consider the following example.
Let there be two men m1 and m2 and two women w1 and w2.
Let m1‘s list of preferences be {w1, w2}
Let m2‘s list of preferences be {w1, w2}
Let w1‘s list of preferences be {m1, m2}
Let w2‘s list of preferences be {m1, m2}
The matching { {m1, w2}, {w1, m2} } is not stable because m1 and w1 would prefer each other over their assigned partners. The matching {m1, w1} and {m2, w2} is stable because there are no two people of opposite sex that would prefer each other over their assigned partners.
It is always possible to form stable marriages from lists of preferences (See references for proof). Following is Gale–Shapley algorithm to find a stable matching:
The idea is to iterate through all free men while there is any free man available. Every free man goes to all women in his preference list according to the order. For every woman he goes to, he checks if the woman is free, if yes, they both become engaged. If the woman is not free, then the woman chooses either says no to him or dumps her current engagement according to her preference list. So an engagement done once can be broken if a woman gets better option.
Following is complete algorithm from Wiki
Initialize all men and women to free
while there exist a free man m who still has a woman w to propose to
{
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}
Input & Output: Input is a 2D matrix of size (2*N)*N where N is number of women or men. Rows from 0 to N-1 represent preference lists of men and rows from N to 2*N – 1 represent preference lists of women. So men are numbered from 0 to N-1 and women are numbered from N to 2*N – 1. The output is list of married pairs.
Following is C++ implementation of the above algorithm.
// C++ program for 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 lisr of w, then w prefers her
// cirrent 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 numbereed as N to 2N-1.
void stableMarriage(int prefer[2*N][N])
{
// Stores partner of women. This is our output array that
// stores paing 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 (Note that the partnership maybe changed
// later). 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 Else
} // End of the for loop that goes to all women in m's list
} // End of main while loop
// Print the solution
cout << "Woman Man" << endl;
for (int i = 0; i < N; i++)
cout << " " << i+N << " " << 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;
}
Output:
Woman Man
4 2
5 1
6 3
7 0
// C++ program for 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 lisr of w, then w prefers her
// cirrent 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 numbereed as N to 2N-1.
void stableMarriage(int prefer[2*N][N])
{
// Stores partner of women. This is our output array that
// stores paing 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 (Note that the partnership maybe changed
// later). 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 Else
} // End of the for loop that goes to all women in m's list
} // End of main while loop
// Print the solution
cout << "Woman Man" << endl;
for (int i = 0; i < N; i++)
cout << " " << i+N << " " << 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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.