Gale Shapley Java Program
Posted on by admin
Gale Shapley Java Program Average ratng: 4,7/5 7306 reviews
Code:
public class GaleShapley
{
private int N, engagedCount;
private String[][] menPref;
private String[][] womenPref;
private String[] men;
private String[] women;
private String[] womenPartner;
private boolean[] menEngaged;
/** Constructor **/
public GaleShapley(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 Algorithmn');
/** list of men **/
String[] m = {'M1', 'M2', 'M3', 'M4', 'M5'};
/** list of women **/
String[] w = {'W1', 'W2', 'W3', 'W4', 'W5'};
/** men preference **/
String[][] mp = {{'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'}};
/** women preference **/
String[][] wp = {{'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'}};
GaleShapley gs = new GaleShapley(m, w, mp, wp);
}
}
Output:
Gale Shapley Marriage Algorithm
Couples are :
M4 W1
M2 W2
M5 W3
M3 W4
M1 W5
More Java Programs:
Gale Shapley Java Program Pdf
- Following is Gale–Shapley algorithm. Program for stable marriage problem #include Java Linked Lists Mathematical. 002, import java.util. The Gale-Shapely algorithm only unmatches a woman if the new proposer is preferred to the existing proposer. Also, to note: List manList= m.
- Solve the Stable marriage problem using the Gale/Shapley algorithm. Problem description Given an equal number of men and women to be paired for marriage, each man. Write a program to implement the Gale-Shapley algorithm for nding a stable maximum matching in a complete. Questions involving programming Java should be used.
Gale Shapley Java Programming
2 A JAVA Program for the Gale-Shapley Algorithm The Gale-Shapley algorithm was developed to pair men and women who had expressed their individual. 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. This is a Java Program to Implement Gale Shapley Algorithm. Gale Shapley Algorithm is used to solve the stable marriage problem (SMP). SMP is the problem of finding a stable matching between two sets of elements given a set of preferences for each element.