JAVA IMPLEMENTATION OF GALE SHAPLEY ALGORITHM - USE HELPER CLASS PROVIDED BELOW

Question

JAVA IMPLEMENTATION OF GALE SHAPLEY ALGORITHM - USE HELPER CLASS PROVIDED BELOW (Preferences.java)

In this problem we will consider a version of the problem for professors and students and their fully ordered list of preferences. The Stable Matching Problem, as discussed in the text, assumes that all men and women have a fully ordered list of preferences. In this problem we will consider a version of the problem for professors and students and their fully ordered list of preferences. Note that ties in preference lists are not allowed. As before we have a set P of n professors and a set S of n students. Assume each professor and each student ranks the members of the opposite group.

Part 2: Implement Gale-Shapley Algorithm
In order to solve this matching problem more efficiently, you need to implement Gale-Shapley Al- gorithm and give a solution for Professors Optimal Matching. For implementation, we provide you with again with Preferences.java and you will put your implementation to Assignment1.java file under stableMatchGaleShapley(). This function will again return ArrayList, described in previous part. Keep note that your algorithm should run in O(n2) time. Make sure that a student can compare between his current professor and another professor in constant time.

public static ArrayList<Integer> stableMatchGaleShapley(Preferences preferences) {}

PREFERENCES.JAVA

import java.util.ArrayList;

/**
* Class to provide input to Stable Matching algorithms
*/
public class Preferences {
/** Number of professors. */
private int numberOfProfessors;

/** Number of students. */
private int numberOfStudents;

/** A list containing each professor's preference list. */
private ArrayList<ArrayList<Integer>> professors_preference;

/** A list containing each student's preference list. */
private ArrayList<ArrayList<Integer>> students_preference;

public Preferences(int numberOfProfessors, int numberOfStudents,
ArrayList<ArrayList<Integer>> professors_preference,
ArrayList<ArrayList<Integer>> students_preference) {
this.numberOfProfessors = numberOfProfessors;
this.numberOfStudents = numberOfStudents;
this.professors_preference = professors_preference;
this.students_preference = students_preference;
}

public int getNumberOfProfessors() {
return numberOfProfessors;
}

public void setNumberOfProfessors(int numberOfProfessors) {
this.numberOfProfessors = numberOfProfessors;
}

public int getNumberOfStudents() {
return numberOfStudents;
}

public void setNumberOfStudents(int numberOfStudents) {
this.numberOfStudents = numberOfStudents;
}

public ArrayList<ArrayList<Integer>> getProfessors_preference() {
return professors_preference;
}

public void setProfessors_preference(ArrayList<ArrayList<Integer>> professors_preference) {
this.professors_preference = professors_preference;
}

public ArrayList<ArrayList<Integer>> getStudents_preference() {
return students_preference;
}

public void setStudents_preference(ArrayList<ArrayList<Integer>> students_preference) {
this.students_preference = students_preference;
}
}

Explanation / Answer

GaleShapleyAlgo.java

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template fl, choose Tools | Templates
* and open the template in the editor.
*/
package main;

/**
*
* @author Akshay Bisht
*/
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class GaleShapleyAlgo
{
private ArrayList<ArrayList<Integer>> males = new ArrayList<ArrayList<Integer>>();
private ArrayList<ArrayList<Integer>> females = new ArrayList<ArrayList<Integer>>();
public int no;
public static void main(String[] args) throws FileNotFoundException
{
File fl = new File("file.in");
GaleShapleyAlgo gsa = new GaleShapleyAlgo();
gsa.readIp(fl);
System.out.println("number of boys and girls = " + gsa.no);
ArrayList<Integer> al = gsa.purposes();
System.out.println(al);

}
public void readIp(File fl) throws FileNotFoundException
{
Scanner sc = new Scanner(fl);
no = sc.nextInt();

for(int uu = 0; uu < no; uu++)
{
ArrayList<Integer> tempo = new ArrayList<Integer>();
for (int qq = 0; qq < no; qq++)
{
int tempInteg = sc.nextInt() -1;
tempo.add(tempInteg);
}
males.add(tempo);
}

for(int uu = 0; uu < no; uu++)
{
ArrayList<Integer> tempo = new ArrayList<Integer>();
for(int qq = 0; qq < no; qq++)
{
int tempInteg = sc.nextInt()-1;
tempo.add(tempInteg);
}
females.add(tempo);
}
sc.close();
}

public ArrayList<Integer> purposes()
{
ArrayList<Integer> op = new ArrayList<Integer>();

Queue<Integer> lst = new LinkedList<Integer>();
for(int uu = 0; uu < no; uu++)
{
lst.add(uu);
}
ArrayList<Integer> men = new ArrayList<Integer>();
ArrayList<Integer> women = new ArrayList<Integer>();
for(int uu = 0; uu < no; uu++)
{
men.add(0);
women.add(0);
op.add(-1);
}
int pri = males.get(lst.peek()).get(men.get(lst.peek()));
op.set(pri, lst.peek()+1);
men.set(lst.peek(), men.get(lst.peek())+1);
lst.remove();

while(!lst.isEmpty())
{
int indicePref = males.get(lst.peek()).get(men.get(lst.peek())) ;
if(op.get(indicePref) < 0)
{
op.set(indicePref, lst.peek()+1);
men.set(lst.peek(), men.get(lst.peek())+1);
lst.remove();
}
else
{
int ranksAttach = findRank(females.get(indicePref), op.get(indicePref).intValue());
int rnkFut = findRank(females.get(indicePref),op.get(indicePref).intValue());
if(rnkFut < ranksAttach)
{
lst.add(op.get(indicePref));
op.set(indicePref, lst.peek()+1);
men.set(lst.peek(), men.get(lst.peek())+1);
lst.remove();
}
else
{
men.set(lst.peek(), men.get(lst.peek())+1);

}
}
}
return op;
}
public int findRank(ArrayList<Integer> pref, Integer individual)
{
int orders = 0;
for(int uu = 0; uu < pref.size(); uu++)
{
if(pref.get(uu).equals(individual))
{
orders = uu;
}
}
return orders;
}
}

Rate an upvote....Thankyou

Hope this helps......

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.