Part 3: Matching with Costs In this problem we will consider a version of the pr
ID: 3889103 • Letter: P
Question
Part 3: Matching with Costs
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.
In this part, we will be having costs for the stable matching algorithm. What this means is that there are going to be two stable matching combinations (one will be Professors Optimal and one will be Students Optimal). The way we calculate the costs is as follows.
Lets take the example of a professor. Suppose his preference list is {s1,s2,s3,s4,s5}. If the final pair comes to be (p1,s4), then cost of this for professor is going to be 3. (4-1=3). Similarly suppose if the preference list of student 4 was {p3,p2,p1,p4,p5}, then his cost will be 2. Thus the cost of a pair to someone is the difference in rank of his most preferred choice and rank of the person currently assigned to him.
Now, you need to apply the stable matching algorithm for both professors optimal and students optimal. The output will be the stable pairs and their costs. Your output should look like this (p1,s4,3,1) where this result shows index or professor, index of student, cost to professor and cost to student respectively. You should put your implementation to same file(Assignment1.java) under stableMatchCosts() function. For output, you are provided with Cost.java class and the function should return an ArrayList of Costs. Your input to the function will be same as previous part, an instance of Preferences class.
Cost.java and Preferences.java are provided below. Please implement stableMatchCosts() function.
// Part3: Matching with Costs
public static ArrayList<Cost> stableMatchCosts(Preferences preferences) {}
Cost.java
/**
* Cost object for Assignment 1 - Part 3
* This object helps you to return 4 fields at once.
* The meaning of cost is described in the assignment.
*/
public class Cost {
private int indexOfProfessor;
private int indexOfStudent;
private int costToProfessor;
private int costToStuent;
public Cost(int indexOfProfessor, int indexOfStudent, int costToProfessor, int costToStuent) {
this.indexOfProfessor = indexOfProfessor;
this.indexOfStudent = indexOfStudent;
this.costToProfessor = costToProfessor;
this.costToStuent = costToStuent;
}
public int getIndexOfProfessor() {
return indexOfProfessor;
}
public void setIndexOfProfessor(int indexOfProfessor) {
this.indexOfProfessor = indexOfProfessor;
}
public int getIndexOfStudent() {
return indexOfStudent;
}
public void setIndexOfStudent(int indexOfStudent) {
this.indexOfStudent = indexOfStudent;
}
public int getCostToProfessor() {
return costToProfessor;
}
public void setCostToProfessor(int costToProfessor) {
this.costToProfessor = costToProfessor;
}
public int getCostToStuent() {
return costToStuent;
}
public void setCostToStuent(int costToStuent) {
this.costToStuent = costToStuent;
}
}
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> professors_preference;
/** A list containing each student's preference list. */
private ArrayList> students_preference;
public Preferences(int numberOfProfessors, int numberOfStudents,
ArrayList> professors_preference,
ArrayList> 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> getProfessors_preference() {
return professors_preference;
}
public void setProfessors_preference(ArrayList> professors_preference) {
this.professors_preference = professors_preference;
}
public ArrayList> getStudents_preference() {
return students_preference;
}
public void setStudents_preference(ArrayList> students_preference) {
this.students_preference = students_preference;
}
}
Explanation / Answer
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;
}
}