1. Implement Gale-Shapley Algorithm for computing Stable Marriage Assignment in
ID: 3905536 • Letter: 1
Question
1. Implement Gale-Shapley Algorithm for computing Stable Marriage Assignment in any language, such as Python, Java, C++ or MATLAB, using the approach and data structures described in the first two Chapters of the Kleinberg and Tardos text. The input file should include the number of subjects, n, preference list for men and women one line for each.
n
m1: w11, w12, ..., w1n
...
...
mn: wn1, wn2, ..., wnn
w1: m11, m12, ..., m1n
...
...
wn: mn1, mn2, ..., mnn
a) Write the output, explicitly checking to see that it is a stable match (It requires a separate function to check). Turn in sample inputs and corresponding outputs in separate files.
b) Write a function to create preference lists for men and women. Function should take number of men(women), say n, create preferences and output them.
C) Run the algorithm on several instances of the problem for n = 10 with different input files and plot the variation in the running time.
d) Run the algorithm on several instances of the problem for n = 10 with the same input file and plot the variation in the running time.
e) Run the algorithm on problem instances with n = 10, 15, 20, 50, 100, and plot the average running time as a function of the problem input size (n).
Explanation / Answer
Implemented JavaSource code:-
--------------------------------------
package com.ibm;
import java.util.Scanner;
public class Gale_Shapley
{
int Size,engagedCount;
String[][] menpreference;
String[][] womenpreference;
String[] menslist;
String[] womenslist;
String[] womenPartner;
boolean[] menEngaged;
public Gale_Shapley(String[] menslist, String[] womenslist, String[][] menpreference, String[][] womenpreference)
{
this.menslist=menslist;
this.womenslist=womenslist;
this.menpreference=menpreference;
this.womenpreference=womenpreference;
this.Size=menpreference.length;
menEngaged = new boolean[Size];
womenPartner = new String[Size];
engagedCount = 0;
}
void CalculateMatches()
{
while (engagedCount<Size)
{
int free;
for(free=0;free<Size;free++)
if (!menEngaged[free])
break;
for(int i=0;i<Size && !menEngaged[free]; i++)
{
int index = WomenChoice(menpreference[free][i]);
if (womenPartner[index]==null)
{
womenPartner[index]=menslist[free];
menEngaged[free] = true;
engagedCount++;
}
else
{
String currentPartner = womenPartner[index];
if (Preference(currentPartner, menslist[free], index))
{
womenPartner[index] = menslist[free];
menEngaged[free] = true;
menEngaged[MensChoice(currentPartner)] = false;
}
}
}
}
printCouples();
}
private void printCouples()
{
System.out.println(" ** The Couples are :*** ");
for (int i=0;i<Size;i++)
{
System.out.println(womenPartner[i] +" "+ womenslist[i]);
}
}
private int MensChoice(String currentPartner)
{
for(int i=0;i<Size;i++)
if (menslist[i].equals(currentPartner))
return i;
return -1;
}
private boolean Preference(String currentPartner, String newPartner,int index)
{
for(int i=0;i<Size;i++)
{
if (womenpreference[index][i].equals(newPartner))
return true;
if (womenpreference[index][i].equals(currentPartner))
return false;
}
return false;
}
private int WomenChoice(String string)
{
for (int i = 0; i < Size; i++)
{
if (womenslist[i].equals(string))
return i;
}
return -1;
}
public static void main(String[] args) throws CloneNotSupportedException
{
Scanner sc=new Scanner(System.in);
System.out.println(" -----------------------------------------------------");
System.out.println("*** Welcome to the GaleShapley Marriage Algorithm ****");
System.out.println(" -----------------------------------------------------");
String[] menslist = {"M1", "M2", "M3", "M4", "M5"};//list of Mens
String[] womenslist = {"W1", "W2", "W3", "W4", "W5"}; // list of women
String[][] menpreference = {{"W5", "W2", "W3", "W4", "W1"},{"W2", "W5", "W1", "W3", "W4"},{"W4", "W3", "W2", "W1", "W5"}, {"W1", "W2", "W3", "W4", "W5"},{"W5", "W2", "W3", "W4", "W1"}};
String[][] womenpreference = {{"M5", "M3", "M4", "M1", "M2"},{"M1", "M2", "M3", "M5", "M4"}, {"M4", "M5", "M3", "M2", "M1"}, {"M5", "M2", "M1", "M4", "M3"},{"M2", "M1", "M4", "M3", "M5"}};
Gale_Shapley obj = new Gale_Shapley(menslist, womenslist, menpreference, womenpreference);
obj.CalculateMatches();
//obj.clone();
sc.close();
}
}
Sample Output:-
------------------
-----------------------------------------------------
*** Welcome to the GaleShapley Marriage Algorithm ****
-----------------------------------------------------
** The Couples are :***
M4 W1
M2 W2
M5 W3
M3 W4
M1 W5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.