Question

Implement the Gale Shapley algorithm using JsFiddle.

Must have a sample data set of 5 males and 5 females each with defined listings

• Can treat people as indexes, Person 0 - Person 4 or whatever works.

Answer 1

Gale Shapley algorithm using JsFiddle:

Gale Shapley algorithm:

It is used for stable marriage problem(SMP). Algorithm as follows:

function stableMatching{

Initialize all m belongs to M and w belongs to W to free

while there is a man m who is free and hasn't proposed to every woman

choose such a man m

Let w be the highest-ranked woman in m's Preference list to whom m has not yet

If w is free then

(m,w) become engaged

Else w is currently engaged to m'

If w prefers m' to m then

m remains free

Else w prefers m to m'

(m,w) become engaged

m' becomes free

Endif

Endif

Endwhile

return the set S of engaged pairs

Java Program

import java.io.*;

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 Galesshapley(String[] m, String[] w, String[][] mp, String[][] wp){

N =m.length;

engagedcount=0;

men=m;

women=w;

menpref=mp;

womenpref=wp;

menengaged = new boolean[N];

womenpartner =new String[N];

calcmatches();

}

//function calculate all the 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 boolen 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 Algorithm");

String[] m={"M1","M2","M3","M4","M5"};

String[] w={"W1","W2","W3","W4","W5"};

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"}};

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 Shapely Algorithm

Couples are:

M4 W1

M2 W2

M5 W3

M3 W4

M1 W5