Java Linear Data Structures Stable Marriage Problem Project 3 100 points Due Thu
ID: 3589815 • Letter: J
Question
Java
Linear Data Structures
Stable Marriage Problem
Project 3 100 points Due Thursday October 12
Note: You must do your own work. Solutions for this problem exist on the Internet. Code copied from the Internet will get a grade of 0. Code from the Internet often uses the Map, HashMap, and ArrayList data strutures. These are not allowed. You must use the data structures defined in the text.
For this assignment, you may work in pairs. There is no extra credit for working alone.
The assignment is to write a console-based program to solve the Stable Matching Problem using the Gale-Shapley algorithm. You must use a linked list for the preference list of each man and woman. 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,
1. the number n of men and women,
2. the names of the n men,
3. the names of the n women,
4. the list of preferences for each of the n men, and
5. the list of preferences for each 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:
1. Ask the user for the name of the input file
2. Display the number of men and women, and the lists of men and women
3. Display the list of men’s preferences and the list of women’s preferences
4. Ask the user to select one of the following:
Men Propose
Women Propose
5. Ask the user for the go-ahead to apply the Gale-Shapley algorithm
6. Display the list of marriages.
The submission should include a printout of using the data given above.
Extra Credit: (30 points) Construct a GUI using JavaFX. The GUI must be defined in a separate class and follow the posted coding guidelines. You must declare all variables at the top of the class or method, and must not initialize variables in the declaration. (10 points for correctness of the GUI, 10 for the efficacy and attractiveness of the GUI, and 10 for following the coding guidelines nicely.)
Explanation / Answer
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.StringTokenizer;
//Class GaleShapley definition
public class GaleShapley
{
//Counter for number of engaged
private int N, engagedCount;
//Matrix to store preference men
private String[][] menPref;
//Matrix to store preference women
private String[][] womenPref;
//To store men names
private String[] men;
//To store women names
private String[] women;
//To sore women partner name
private String[] womenPartner;
//To sore men partner name
private boolean[] menEngaged;
//Method to read data from file and store it
void readFile()throws IOException
{
//FileReader class object created
FileReader fr = new FileReader("MaleFemale.txt");
//BufferedReader class object created
BufferedReader br = new BufferedReader(fr);
//Reads number of male and female number i.e., the first data in the file
int n = Integer.parseInt(br.readLine());
//Initializes member string array and matrix
men = new String[n];
women = new String[n];
womenPref = new String[n][];
menPref = new String[n][];
//Allocates size to each column
for(int c = 0; c < n; c++)
{
womenPref[c] = new String[20];
menPref[c] = new String[20];
}//End of for loop
String ss;
StringTokenizer str;
//Reads men names
ss = br.readLine();
str = new StringTokenizer(ss);
//Loops till n
for(int t = 0; t < n; t++)
{
//Stores each name in the array
men[t] = str.nextToken();
}//End of for loop
//Reads women name
ss = br.readLine();
str = new StringTokenizer(ss);
//Loops till n
for(int t = 0; t < n; t++)
{
//Stores each women in the array
women[t] = str.nextToken();
}//End of for loop
//To read heading
ss = br.readLine();
//Men preference
//Loops till n for man preference
for(int r = 0; r < n; r++)
{
ss = br.readLine();
str = new StringTokenizer(ss);
//To skip heading i.e., [Preferences Men:]
str.nextToken();
//Loops till n for man preference names
for(int c = 0; c < n; c++)
menPref[r][c] = str.nextToken();
}//End of for loop
//To read heading
ss = br.readLine();
//Women preference
//Loops till n for woman preference
for(int r = 0; r < n; r++)
{
ss = br.readLine();
str = new StringTokenizer(ss);
//To skip heading i.e., [Preferences Women:]
str.nextToken();
//Loops till n for woman preference names
for(int c = 0; c < n; c++)
womenPref[r][c] = str.nextToken();
}//End of for loop
//Initializes number of members
N = n;
menEngaged = new boolean[N];
womenPartner = new String[N];
}//End of method
//Method to calculate all matches
private void calcMatches()
{
//Loops till
while (engagedCount < N)
{
int free;
//Loops n times to check engaged or not
for (free = 0; free < N; free++)
//Checks each index position of the menEngaged array for not engaged
if (!menEngaged[free])
//Come out of the loop
break;
//Loops till n and menEngaged is false i.e., not engaged
for (int i = 0; i < N && !menEngaged[free]; i++)
{
//Get the index position of the men preference who is free
int index = womenIndexOf(menPref[free][i]);
//Checks if the women partner is null
if (womenPartner[index] == null)
{
//Stores the name of the man in the women partners index position
womenPartner[index] = men[free];
//Sets the man engaged to true
menEngaged[free] = true;
//Increase the engaged counter by one
engagedCount++;
}//End of if condition
//Otherwise
else
{
//Store the women partner name as the current partner
String currentPartner = womenPartner[index];
//Checks if women prefers new partner over old assigned partner
if (morePreference(currentPartner, men[free], index))
{
//Stores the men name in the women partner index position
womenPartner[index] = men[free];
//Set the man engaged free index position to true i.e., men is engaged
menEngaged[free] = true;
//Set the men engaged name of the men in current position to false
menEngaged[menIndexOf(currentPartner)] = false;
}//End of if condition
}//End of else
}//End of for loop
}//End of while loop
//Calls the method to display couples
printCouples();
}//End of method
//Method to check if women prefers new partner over old assigned partner
private boolean morePreference(String curPartner, String newPartner, int index)
{
//Loops N times
for (int i = 0; i < N; i++)
{
//Checks women preference name at row index position and column i index position is equal to new partner name then return true
if (womenPref[index][i].equals(newPartner))
return true;
//Checks women preference name at row index position and column i index position is equal to current partner name then return false
if (womenPref[index][i].equals(curPartner))
return false;
}//End of for loop
return false;
}//End of method
//Method to get men index
private int menIndexOf(String str)
{
//Loops N times
for (int i = 0; i < N; i++)
//Checks men name at index position i is equal to the name passed as parameter
if (men[i].equals(str))
//Return the index position
return i;
//Returns -1 for not found
return -1;
}//End of method
//Method to get women index
private int womenIndexOf(String str)
{
//Loops N times
for (int i = 0; i < N; i++)
//Checks women name at index position i is equal to the name passed as parameter
if (women[i].equals(str))
//Return the index position
return i;
//Returns -1 for not found
return -1;
}//End of method
//Method to print couples
public void printCouples()
{
System.out.println(" List of marriages couples are ");
//Loops N times
for (int i = 0; i < N; i++)
{
System.out.println(womenPartner[i] +" "+ women[i]);
}//End of for loop
}//End of method
//Method to display men names
void displayMen()
{
System.out.print(" Men: ");
//Loops N times
for(int x = 0; x < N; x++)
System.out.print(men[x] + " ");
}//End function
//Method to display women names
void displayWomen()
{
System.out.print(" Women: ");
//Loops N times
for(int x = 0; x < N; x++)
System.out.print(women[x] + " ");
}//End function
//Method to display men preferences
void displayMenPreferences()
{
System.out.print(" Men's Preferences: ");
//Loops N times for row
for(int x = 0; x < N; x++)
{
//Loops N times for column
for(int y = 0; y < N; y++)
System.out.print(menPref[x][y] + " ");
System.out.println();
}//End for loop
}//End function
//Method to display women's preferences
void displayWomenPreferences()
{
System.out.print(" Womeen's Preferences: ");
//Loops N times for row
for(int x = 0; x < N; x++)
{
//Loops N times for column
for(int y = 0; y < N; y++)
System.out.print(womenPref[x][y] + " ");
System.out.println();
}//End for loop
}//End function
//Main function
public static void main(String[] args) throws IOException
{
//Creates GaleShapley class object
GaleShapley gs = new GaleShapley();
//Calls the readFile method to read data from file
gs.readFile();
//Displays number of men and women
System.out.println(" Number of men and women: " + gs.N);
//Displays men names
gs.displayMen();
//Displays women names
gs.displayWomen();
//Displays men preferences
gs.displayMenPreferences();
//Displays women preferences
gs.displayWomenPreferences();
//Calls the method to match pair
gs.calcMatches();
}//End of main method
}//End of class
Sample Run:
Number of men and women: 5
Men: Brian George John Robert Stephen
Women: Anne Joyce Nancy Patricia Susan
Men's Preferences:
Susan Joyce Nancy Patricia Anne
Nancy Anne Joyce Susan Patricia
Patricia Susan Joyce Anne Nancy
Joyce Anne Susan Nancy Patricia
Nancy Joyce Patricia Susan Anne
Womeen's Preferences:
John Brian Stephen Robert George
George John Stephen Robert Brian
George Brian Robert Stephen John
George Stephen John Brian Robert
Brian George Stephen John Robert
List of marriages couples are
Robert Anne
Stephen Joyce
George Nancy
John Patricia
Brian Susan
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.