I'm working on a stable matching problem implementation in Java, where the input is provided via a text file. The problem involves matching a set of men to a set of women based on their preferences.
Here's an example of the desired input format:
2
1 2
2 1
2 1
1 2
And the desired output:
Output when men propose:
{(1,1), (2,2)}
Output when women propose:
{(1,2), (2,1)}
I've implemented the Gale-Shapley algorithm for both men proposing and women proposing, but I'm encountering some issues with the output.
For the input above, my output is as follows:
Output when men propose:
{(1,), (2,)}
Output when women propose:
{(1,2), (2,1)}
It seems that the output for men proposing is not correct. Similarly, when I use another testcase (input2.txt) with the following input:
3
1 2 3
2 1 3
1 2 3
2 1 3
1 2 3
1 2 3
The expected output is:
Output when men propose:
{(1,1), (2,2) , (3,3)}
Output when women propose:
{(1,2),(2,1), (3,3)}
But I'm getting the same output as if I never changed from the input files.
Here's the relevant part of my code:
try (BufferedReader br = new BufferedReader(new FileReader(fileName))) {
String line;
int lineCount = 0;
while ((line = br.readLine()) != null) {
line = line.trim();
if (line.isEmpty()) {
continue;
}
if (lineCount == 0) {
numPpl = Integer.parseInt(line);
} else {
String[] parts = line.split(" ");
String person;
Integer[] preferences;
if (lineCount <= numPpl) {
person = "M" + parts[0];
} else {
person = "W" + parts[0];
}
preferences = new Integer[numPpl];
// Extract preferences and store them
for (int i = 0; i < numPpl; i++) {
if (i + 1 < parts.length) { // Check if index is within bounds
preferences[i] = Integer.parseInt(parts[i + 1]);
} else {
// Handle case where preferences are missing
// You can choose to set it to a default value or throw an exception
// Here, I'm setting it to -1 as an example
preferences[i] = -1;
}
}
if (lineCount <= numPpl) {
menPrefs.put(person, preferences);
} else {
womenPrefs.put(person, preferences);
}
}
lineCount++;
}
} catch (IOException e) {
e.printStackTrace();
}
I've tried to fix the issue by adjusting the loop where preferences are extracted and stored, but it resulted in an ArrayIndexOutOfBoundsException.
Could someone please help me identify and fix the issue with my implementation?
For reference, here is my whole code
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
public class project1 {
public static void main(String[] args) {
if (args.length != 1) {
System.out.println("Usage: java project1 input.txt");
return;
}
String fileName = args[0];
HashMap<String, Integer[]> menPrefs = new HashMap<>();
HashMap<String, Integer[]> womenPrefs = new HashMap<>();
int numPpl = 0;
try (BufferedReader br = new BufferedReader(new FileReader(fileName))) {
String line;
int lineCount = 0;
while ((line = br.readLine()) != null) {
line = line.trim();
if (line.isEmpty()) {
continue;
}
if (lineCount == 0) {
numPpl = Integer.parseInt(line);
} else {
String[] parts = line.split(" ");
String person;
Integer[] preferences;
if (lineCount <= numPpl) {
person = "M" + parts[0];
} else {
person = "W" + parts[0];
}
preferences = new Integer[numPpl];
// Extract preferences and store them
for (int i = 0; i < numPpl; i++) {
if (i + 1 < parts.length) { // Check if index is within bounds
preferences[i] = Integer.parseInt(parts[i + 1]);
} else {
// Handle case where preferences are missing
// You can choose to set it to a default value or throw an exception
// Here, I'm setting it to -1 as an example
preferences[i] = -1;
}
}
if (lineCount <= numPpl) {
menPrefs.put(person, preferences);
} else {
womenPrefs.put(person, preferences);
}
}
lineCount++;
}
} catch (IOException e) {
e.printStackTrace();
}
// Perform Gale-Shapley Algorithm with men proposing
HashMap<String, String> pairsMen = project1Men(menPrefs, womenPrefs);
// Perform Gale-Shapley Algorithm with women proposing
HashMap<String, String> pairsWomen = project1Women(menPrefs, womenPrefs);
// Print the output
System.out.println("Output when men propose:");
printPairs(pairsMen);
System.out.println("\nOutput when women propose:");
printPairs(pairsWomen);
}
// Gale-Shapley Algorithm with men proposing
private static HashMap<String, String> project1Men(HashMap<String, Integer[]> menPrefs,
HashMap<String, Integer[]> womenPrefs) {
HashMap<String, String> pairs = new HashMap<>();
HashMap<String, Integer> next = new HashMap<>();
for (String man : menPrefs.keySet()) {
next.put(man, 0);
pairs.put(man, "-");
}
while (pairs.containsKey(("-"))) {
for (String man : menPrefs.keySet()) {
if (!pairs.get(man).equals("-")) {
continue; // Already paired
}
int currentWomen = next.get(man);
String women = "W" + menPrefs.get(man)[currentWomen];
int currentMan = -1;
for (String m : pairs.keySet()) {
if (pairs.get(m).equals(women)) {
currentMan = Integer.parseInt(m.substring(1));
break;
}
}
if (currentMan == -1) {
pairs.put(man, women);
} else {
int rankMan = 0, rankCurrMan = 0;
for (int i = 0; i < womenPrefs.get(women).length; i++) {
if (womenPrefs.get(women)[i] == Integer.parseInt(man.substring(1))) {
rankMan = i;
}
if (womenPrefs.get(women)[i] == currentMan) {
rankCurrMan = i;
}
}
if (rankMan < rankCurrMan) {
pairs.put(man, women);
pairs.put("M" + currentMan, "-");
}
}
next.put(man, currentWomen + 1);
}
}
return pairs;
}
// Gale-Shapley Algorithm with women proposing
private static HashMap<String, String> project1Women(HashMap<String, Integer[]> menPrefs,
HashMap<String, Integer[]> womenPrefs) {
HashMap<String, String> pairs = new HashMap<>();
HashMap<String, Integer> next = new HashMap<>();
for (String woman : womenPrefs.keySet()) {
next.put(woman, 0);
pairs.put(woman, "-");
}
while (pairs.containsValue("-")) {
for (String woman : womenPrefs.keySet()) {
if (!pairs.get(woman).equals("-")) {
continue; // Already paired
}
int currentMan = next.get(woman);
String man = "M" + womenPrefs.get(woman)[currentMan];
int currentWoman = -1;
for (String w : pairs.keySet()) {
if (pairs.get(w).equals(man)) {
currentWoman = Integer.parseInt(w.substring(1));
break;
}
}
if (currentWoman == -1) {
pairs.put(woman, man);
} else {
int rankWoman = 0, rankCurrWoman = 0;
for (int i = 0; i < menPrefs.get(man).length; i++) {
if (menPrefs.get(man)[i] == Integer.parseInt(woman.substring(1))) {
rankWoman = i;
}
if (menPrefs.get(man)[i] == currentWoman) {
rankCurrWoman = i;
}
}
if (rankWoman < rankCurrWoman) {
pairs.put(woman, man);
pairs.put("W" + currentWoman, "-");
}
}
next.put(woman, currentMan + 1);
}
}
return pairs;
}
// Method to print the pairs
private static void printPairs(HashMap<String, String> pairs) {
System.out.print("{");
for (String key : pairs.keySet()) {
System.out.print("(" + key.substring(1) + "," + pairs.get(key).substring(1) + ")");
if (!key.equals(pairs.keySet().toArray()[pairs.size() - 1])) {
System.out.print(", ");
}
}
System.out.println("}");
}
}