In this problem we will consider a version of the problem for professors and stu
ID: 3889166 • Letter: I
Question
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
A brute force solution to this problem involves generating all possible permutations of men and women, and checking whether each one is a stable matching, until a stable matching is found. For this assignment, you are provided with Preferences.java class which includes the necessarry input structures for the problem. Please see the comments in Preferences.java file for details. You are also given Assignment1.java file where you will put your implementation for this part under stableMatchBruteForce() function which returns ArrayList<Integer>. This ArrayList should contain information for matching information representing the index of student matched with a professor, -1 is not matched. For example, if ith element of the returned ArrayList is j, than professor i is matched with student j. There might be a stable matching which is neither professor nor student optimal. This is because in a brute force, you are trying to find all possible stable matches. Preferences.java is provided below. Please implement stableMatchBruteForce().
// Part1: Implement a Brute Force Solution
public static ArrayList<Integer> stableMatchBruteForce(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
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;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.