This assignment is to write a console-based program to solve the Stable Matching
ID: 673613 • Letter: T
Question
This assignment is to write a console-based program to solve the Stable Matching Problem using the Gale-Shapley algorithm. You must use the Separation Principle for you code. This means (1) All variables will be declared at the top of the main class, (b) All methods will have a void return type and have no parameters.
For this assignment, you may work in pairs.
See the posting “Stable Matching.ppt” in the Algorithms folder. There are also numerous references to the Gale-Shapley algorithm on the Internet.
The input to the program will be a text file listing, in order,
the number n of men and women,
the names of the n men,
the names of the n women,
the list of preferences for the n men, and
the list of preferences of the n women.
For example, consider the following example of the contents of a file
----------------------------------------------------
5
Brian George John Robert Stephen
Anne Joyce Nancy Patricia Susan
// Preferences Men:
John: Susan Joyce Nancy Patricia Anne
Robert: Nancy Anne Joyce Susan Patricia
Brian: Patricia Susan Joyce Anne Nancy
Stephen: Joyce Anne Susan Nancy Patricia
George: Nancy Joyce Patricia Susan Anne
// Preferences Women:
Nancy: John Brian Stephen Robert George
Joyce: George John Stephen Robert Brian
Patricia: George Brian Robert Stephen John
Anne: George Stephen John Brian Robert
Susan: Brian George Stephen John Robert
----------------------------------------------------
The output will be the list of arranged marriages.
----------------------------------------------------
Marriages:
(Anne,Stephen)
(Joyce,George)
(Susan,John)
(Patricia,Brian)
(Nancy,Robert)
----------------------------------------------------
The program will operate as follows:
Ask the user for the name of the input file
Display the number of men and women, and the lists of men and women
Display the list of men’s preferences and the list of women’s preferences
Ask the user to select one of the following:
Men Propose
Women Propose
Ask the user for the go-ahead to apply the Gale-Shapley algorithm
Display the list of marriages.
The submission should include a printout using the data given above.
2 4 Boys GirlsExplanation / Answer
/** Class Stable_Matching **/
public class Stable_Matching
{
private int N, engagedCount;
private String[][] menPref;
private String[][] womenPref;
private String[] men;
private String[] women;
private String[] womenPartner;
private boolean[] menEngaged;
/** Constructor **/
public Stable_Matching(String[] m, String[] w, String[][] mp, String[][] wp)
{
N = mp.length;
engagedCount = 0;
men = m;
women = w;
menPref = mp;
womenPref = wp;
menEngaged = new boolean[N];
womenPartner = new String[N];
calcMatches();
}
/** function to calculate all matches **/
private void calcMatches()
{
while (engagedCount < N)
{
int free;
for (free = 0; free < N; free++)
if (!menEngaged[free])
break;
for (int i = 0; i < N && !menEngaged[free]; i++)
{
int index = womenIndexOf(menPref[free][i]);
if (womenPartner[index] == null)
{
womenPartner[index] = men[free];
menEngaged[free] = true;
engagedCount++;
}
else
{
String currentPartner = womenPartner[index];
if (morePreference(currentPartner, men[free], index))
{
womenPartner[index] = men[free];
menEngaged[free] = true;
menEngaged[menIndexOf(currentPartner)] = false;
}
}
}
}
printCouples();
}
/** function to check if women prefers new partner over old assigned partner **/
private boolean morePreference(String curPartner, String newPartner, int index)
{
for (int i = 0; i < N; i++)
{
if (womenPref[index][i].equals(newPartner))
return true;
if (womenPref[index][i].equals(curPartner))
return false;
}
return false;
}
/** get men index **/
private int menIndexOf(String str)
{
for (int i = 0; i < N; i++)
if (men[i].equals(str))
return i;
return -1;
}
/** get women index **/
private int womenIndexOf(String str)
{
for (int i = 0; i < N; i++)
if (women[i].equals(str))
return i;
return -1;
}
/** print couples **/
public void printCouples()
{
System.out.println("Couples are : ");
for (int i = 0; i < N; i++)
{
System.out.println(womenPartner[i] +" "+ women[i]);
}
}
/** main function **/
public static void main(String[] args)
{
System.out.println("Gale Shapley Marriage Algorithm ");
/** list of men **/
String[] m = {"Brian", "George", "John", "Robert", "Stephen"};
/** list of women **/
String[] w = {"Anne", "Joyce", "Nancy", "Patricia", "Susan"};
/** men preference **/
String[][] mp = {{"Susan", "Joyce", "Nancy", "Patricia", "Anne"},
{"Joyce", "Susan", "Anne", "Nancy", "Patricia"},
{"Patricia", "Nancy", "Joyce", "Anne", "Susan"},
{"Anne", "Joyce", "Nancy", "Patricia", "Susan"},
{"Susan", "Joyce", "Nancy", "Patricia", "Anne"}};
/** women preference **/
String[][] wp = {{"Stephen", "John", "Robert", "Brian", "George"},
{"Brian", "George", "John", "Stephen", "Robert"},
{"Robert", "Stephen", "John", "George", "Brian"},
{"Stephen", "George", "Brian", "Robert", "John"},
{"George", "Brian", "Robert", "John", "Stephen"}};
Stable_Matching gs = new Stable_Matching(m, w, mp, wp);
}
}