Stable Marriage Problem Objectives: Practice LinkedList You are going to write a

Question

Stable Marriage Problem Objectives: Practice LinkedList You are going to write a program that solves a classic computer science problem known as the stable marriage problem. The input file is divided into men and women and the program tries to pair them so as to generate as many marriages as possible that are all stable. A set of marriages is unstable if yo can find a man and a woman who would rather be married to each other than to their spouses (in whic case, the two would be inclined to divorce their spouses and marry each other). The input file for the program will list all of the men, one per line, followed by a line with just the wor "END" on it, followed by all of the women, one per line, followed by another line with just the word "END" on it. The men and women are numbered by their position in the input file. To make this easi we assign numbers starting at 0 (the first man is #0, the second man is al, and so on; the first woman i #0, the second woman is #1, and so on). Each input line (except the two lines with "END') has a name followed by a colon followed by a list of integers. The integers are the preferences for this particular person. For example, the following input line in the men's section: Joe: 9 7 34 8 19 21 32 5 28 6 31 15 17 24 indicates that the person is named "Joe" and that his first choice for marriage is woman #9, his second choice is woman a7, and so on. Any women not listed are considered unacceptable to Joe. The data fil has been purged of any impossible pa where one person is interested in the other, but the other considers that person unacceptable. Thus, ifa woman appears on Joe's list, then Joe is acceptable to tha There are many ways to approach the stable marriage problem. You are to implement a specific algorithm described below. This is the basic outline: set each person to be free; while (some man m with a nonempty preference list is free) first woman on m's list; if (some man p is engaged to w) setp to be free set mand w to be engaged to each other for (each successor q ofm on w's list) delete w from q's preference list delete qfrom w's preference list

Explanation / Answer

Person.java
import java.util.*;

public class Person {
public static final int NOBODY = -1;

private String name;
private List<Integer> preferences;
private List<Integer> oldPreferences;
private int partner;

public Person(String name) {
this.name = name;
preferences = new ArrayList<Integer>();
oldPreferences = new ArrayList<Integer>();
erasePartner();
}

public void erasePartner() {
partner = NOBODY;
}

public boolean hasPartner() {
return partner != NOBODY;
}

public int getPartner() {
return partner;
}

public void setPartner(int partner) {
this.partner = partner;
}

public String getName() {
return name;
}

public boolean hasChoices() {
return !preferences.isEmpty();
}

public int getFirstChoice() {
return preferences.get(0);
}

public void addChoice(int person) {
preferences.add(person);
oldPreferences.add(person);
}

public List<Integer> getChoices() {
return preferences;
}

public int getPartnerRank() {
return oldPreferences.indexOf(partner) + 1;
}
}

StableMarriage.java

import java.io.*;
import java.util.*;

public class StableMarriage {
public static final String LIST_END = "END";

public static void main(String[] args) throws FileNotFoundException {
Scanner console = new Scanner(System.in);
System.out.print("What is the input file? ");
String fileName = console.nextLine();
Scanner input = new Scanner(new File(fileName));
System.out.println();

List<Person> men = readHalf(input);
List<Person> women = readHalf(input);
makeMatches(men, women);
writeList(men, women, "Matches for men");
writeList(women, men, "Matches for women");
}

public static Person readPerson(String line) {
int index = line.indexOf(":");
Person result = new Person(line.substring(0, index));
Scanner data = new Scanner(line.substring(index + 1));
while (data.hasNextInt()) {
result.addChoice(data.nextInt());
}
return result;
}

public static List<Person> readHalf(Scanner input) {
List<Person> result = new ArrayList<Person>();
String line = input.nextLine();
while (!line.equals(LIST_END)) {
result.add(readPerson(line));
line = input.nextLine();
}
return result;
}

public static void makeMatches(List<Person> list1, List<Person> list2) {

//set m to be free
for (Person m : list1){
m.erasePartner();
}
  
//set w to be free
for (Person w : list2){
w.erasePartner();
}

//define m
for (Person m : list1){
//define w
for (Person w : list2){
//while (some man m with a nonempty preference list is free) {
while (m.hasChoices() && !m.hasPartner()){
//w is first woman on m's list
int choosenWoman = m.getFirstChoice();
//define p
for (Person p : list1){
//if (some man p is engaged to w) {
if (p.getPartner()== choosenWoman){
//p is now free
p.erasePartner();
}
}
//assign m and w to be engaged
m.setPartner(choosenWoman);
list2.get(choosenWoman).setPartner(list1.indexOf(m));

List manList= m.getChoices();
List womanList = w.getChoices();
  
//for (each successor q of m who is on w's list) {
for (int q = womanList.size() - 1; q >= 0; q--){
//delete w from q's preference list and q from w's preference list
if(q > womanList.indexOf(list1.indexOf(m)))
manList.remove(manList.indexOf(m.getFirstChoice()));
womanList.remove(q);
}
}
}
}
}

public static void writeList(List<Person> list1, List<Person> list2,
String title) {
System.out.println(title);
System.out.println("Name Choice Partner");
System.out.println("--------------------------------------");
int sum = 0;
int count = 0;
for (Person p : list1) {
System.out.printf("%-15s", p.getName());
if (!p.hasPartner()) {
System.out.println(" -- nobody");
} else {
int rank = p.getPartnerRank();
sum += rank;
count++;
System.out.printf("%4d %s ", rank,
list2.get(p.getPartner()).getName());
}
}
System.out.println("Mean choice = " + (double) sum / count);
System.out.println();
}
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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