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) { w = first woman on m's list; if (some man p is engaged to w) { set p to be free } set m and w to be engaged to each other for (each successor q of m on w's list) { delete w from q's preference list delete q from w's preference list } } Consider, for example, the following short input: Man 0: 3 0 1 2 Woman 0: 3 0 2 1 Man 1: 1 2 0 3 Woman 1: 0 2 1 3 Man 2: 1 3 2 0 Woman 2: 0 1 2 3 Man 3: 2 0 3 1 Woman 3: 3 0 2 1 // This program reads an input file of preferences and find a stable marriage // scenario. The algorithm gives preference to either men or women depending // upon whether this call is made from main: // makeMatches(men, women); // or whether this call is made: // makeMatches(women, men); 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 men = readHalf(input); List 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 readHalf(Scanner input) { List result = new ArrayList(); String line = input.nextLine(); while (!line.equals(LIST_END)) { result.add(readPerson(line)); line = input.nextLine(); } return result; } public static void makeMatches(List list1, List list2) { //------------------------------------ // Implement your code here //------------------------------------ } public static void writeList(List list1, List 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(); } } import java.util.*; public class Person { public static final int NOBODY = -1; private String name; private List preferences; private List oldPreferences; private int partner; public Person(String name) { this.name = name; preferences = new ArrayList(); oldPreferences = new ArrayList(); 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 getChoices() { return preferences; } public int getPartnerRank() { return oldPreferences.indexOf(partner) + 1; } } input file: Man 0: 3 0 1 2 Man 1: 1 2 0 3 Man 2: 1 3 2 0 Man 3: 2 0 3 1 END Woman 0: 3 0 2 1 Woman 1: 0 2 1 3 Woman 2: 0 1 2 3 Woman 3: 3 0 2 1 END Joe: 9 7 34 8 19 21 32 5 28 6 31 15 17 24 Kevin: 23 25 11 27 8 5 10 0 17 33 30 32 19 13 16 7 18 31 9 12 34 22 1 Arnold: 1 0 12 19 26 27 11 10 17 21 34 29 15 4 14 5 33 22 8 30 28 Herbert: 2 8 5 31 15 20 25 34 9 29 0 David: 31 23 33 14 22 32 12 11 26 8 21 24 25 34 2 18 27 15 19 1 6 0 17 10 Brett: 17 0 15 6 27 21 10 2 20 14 22 3 7 31 13 8 19 4 32 24 9 5 33 18 28 25 12 1 11 30 16 23 34 26 29 Arun: 21 5 34 15 1 12 31 17 28 0 16 Andres: 5 32 22 26 0 4 27 12 9 6 3 15 29 33 7 34 8 30 16 14 11 24 10 13 19 23 1 John: 9 0 18 1 21 20 3 29 24 14 Ted: 18 0 21 29 32 14 26 19 10 24 31 23 1 16 22 11 9 7 5 12 20 Craig: 27 33 8 6 7 21 4 16 26 13 12 Matthew: 26 33 24 22 27 34 7 1 8 21 14 10 3 11 0 4 16 13 32 2 23 20 25 31 19 15 12 28 5 6 30 29 9 18 17 Seth: 13 24 2 18 17 9 31 26 15 14 4 27 22 0 20 33 29 32 28 16 19 30 Cliff: 8 6 13 11 9 3 19 28 33 32 2 34 23 Adrian: 32 9 23 24 1 4 27 11 5 8 12 16 34 17 31 29 3 25 13 30 2 15 22 19 14 0 6 William: 21 24 11 32 4 17 18 16 26 33 22 9 27 0 25 15 8 2 23 10 Martin: 2 6 20 11 7 17 29 24 23 9 3 13 22 12 1 Brian: 6 27 22 25 29 0 3 33 34 32 8 30 28 18 11 23 13 15 19 7 12 9 5 17 Edward: 10 4 12 34 22 0 19 20 5 11 24 16 21 13 7 3 15 28 6 8 25 9 2 1 33 30 31 18 Scott: 22 11 31 7 2 17 18 19 15 26 28 5 30 13 8 32 Sean: 21 7 6 31 33 34 0 16 14 32 17 22 Kirk: 24 5 32 20 28 2 10 27 4 9 30 1 21 7 14 16 29 Norman: 16 19 9 5 29 12 11 23 27 28 32 6 13 26 21 20 30 22 31 1 8 2 15 10 7 18 24 0 25 17 33 Michael: 18 1 4 34 7 12 28 32 16 0 22 Jason: 1 16 2 8 28 32 24 26 25 31 Tom: 22 25 17 16 30 0 21 34 4 27 13 10 20 11 Patrick: 34 33 13 26 21 22 14 10 32 8 1 15 3 29 18 20 2 4 17 30 7 19 28 12 23 24 0 11 31 27 25 Mark: 4 24 25 10 0 21 14 9 12 33 20 16 22 15 32 31 7 3 27 11 34 8 26 23 18 17 29 Gil: 24 9 14 23 1 27 33 12 3 4 Jeff: 10 33 16 29 34 1 3 31 21 0 17 13 27 8 6 24 4 30 18 11 5 32 22 Rich: 30 9 18 8 14 1 7 27 12 0 11 32 33 26 21 5 22 24 4 17 15 19 Derrick: 18 4 24 33 21 3 1 26 29 7 15 11 28 8 19 27 12 Curtis: 18 22 10 26 33 27 7 5 9 17 29 32 19 20 1 16 21 25 30 2 14 15 31 24 8 4 23 34 Eric: 31 26 2 11 0 16 12 8 19 24 17 21 27 6 5 22 14 10 30 13 28 20 7 25 33 23 29 3 9 Nick: 2 32 20 9 26 17 10 24 8 15 29 31 13 22 28 23 34 14 4 1 21 27 7 30 16 5 0 3 11 33 25 12 Ramon: 22 4 7 33 34 2 27 28 21 12 14 26 25 10 5 18 16 13 19 9 30 23 32 3 6 Robert: 23 24 30 6 21 11 29 16 34 9 31 26 14 19 3 22 20 18 7 1 17 25 10 8 Charles: 16 26 2 10 30 32 21 3 9 11 19 33 4 20 1 13 25 34 29 31 17 12 24 0 18 Steve: 19 33 7 17 20 13 24 30 2 15 25 1 11 28 8 0 14 22 29 27 10 18 26 23 Carlos: 20 11 7 15 16 12 13 2 31 3 19 17 6 5 28 9 END Jane: 17 3 14 18 12 38 6 26 22 25 30 33 1 2 20 9 11 37 8 27 7 29 15 4 5 34 23 Mary-Anne: 23 18 22 11 29 1 5 7 36 28 21 37 30 4 6 32 31 2 38 8 24 16 9 34 26 14 Elizabeth: 38 21 4 24 22 39 13 11 15 34 33 37 5 3 18 19 26 32 16 12 14 35 Eleanor: 8 14 37 36 29 35 33 28 26 5 7 31 17 18 16 39 13 34 27 11 Trudy: 37 32 10 2 23 30 11 14 12 34 7 29 15 21 18 5 25 26 31 27 28 35 Maria: 21 7 0 1 18 22 33 34 11 29 17 2 30 5 32 6 9 39 35 14 19 3 Helena: 35 16 14 13 0 5 11 20 18 22 17 36 33 39 29 4 10 7 Crystal: 10 34 21 26 23 30 11 0 19 31 5 35 18 38 17 36 27 16 20 22 39 32 33 1 9 7 Susan: 2 33 1 24 15 4 10 14 19 29 0 22 36 5 13 32 30 27 7 38 18 11 34 31 17 26 3 Robyn: 35 16 3 11 12 22 17 36 15 27 14 30 39 7 18 8 0 9 5 13 32 34 28 1 37 21 33 Moon-Star: 11 9 1 7 18 35 32 21 4 38 34 37 26 27 29 15 25 22 33 2 5 36 Debbie: 17 5 7 11 19 2 13 33 26 22 30 27 29 39 34 14 38 16 4 18 37 15 25 1 9 31 36 Nichole: 16 14 2 22 28 7 6 26 11 33 1 5 35 27 17 23 10 4 31 18 37 34 39 9 30 Jennifer: 16 5 18 11 14 35 29 1 26 7 13 12 17 33 10 19 37 25 38 22 34 39 Stephanie: 11 27 20 12 9 26 32 30 36 35 21 4 28 33 38 34 2 14 8 7 5 Mary: 3 2 4 5 7 30 11 15 38 17 14 6 32 12 22 18 34 0 39 19 26 27 31 Tara: 1 33 15 32 20 34 9 36 22 23 27 25 6 39 11 7 24 21 29 18 14 12 35 5 37 10 Rachana: 29 1 2 34 15 12 19 37 14 22 5 17 6 11 0 30 25 38 33 32 39 20 16 36 27 4 26 Farah: 5 4 18 37 11 8 26 9 23 19 32 35 27 22 17 12 30 29 36 31 1 38 15 Yvette: 2 4 1 19 14 13 17 30 18 37 5 12 7 9 32 36 35 11 0 31 26 22 33 38 39 Anna: 27 5 9 16 21 18 32 39 34 22 3 25 38 36 11 8 26 12 33 37 Irene: 34 2 5 10 33 9 36 0 15 31 32 27 8 20 30 21 22 25 29 26 35 37 18 4 6 11 Sylvia: 36 11 23 9 12 16 7 5 33 4 38 34 19 27 30 17 1 20 35 15 25 18 14 2 22 26 29 32 Caroline: 38 26 15 28 16 11 17 9 27 22 35 7 14 5 33 36 1 32 34 13 4 Wendy: 5 36 34 12 27 22 32 18 15 21 7 31 9 8 26 4 14 11 38 33 24 28 37 30 16 29 0 Marla: 34 25 14 36 37 32 18 26 1 33 27 35 15 3 17 38 4 5 11 22 24 Kim: 22 10 35 15 37 38 33 7 26 31 34 27 24 36 2 32 9 30 5 4 19 12 11 Angie: 30 12 5 15 29 25 10 22 2 17 4 34 32 21 27 7 31 26 11 1 14 38 35 33 28 Tessa: 22 39 33 26 5 17 23 34 35 38 21 12 24 0 2 31 19 13 18 6 11 Althea: 17 11 14 22 26 9 2 3 29 36 7 31 12 34 5 27 8 38 37 33 21 32 16 Lucy: 26 30 37 38 19 17 14 22 11 25 7 29 32 34 1 5 33 18 12 36 21 35 2 Julie: 27 39 4 5 11 22 18 19 26 34 20 36 14 33 1 32 0 37 29 12 9 24 3 6 Jean: 34 11 14 21 22 7 19 29 30 35 37 9 20 23 27 5 13 26 1 0 24 17 32 15 12 4 Maude: 5 28 29 1 15 37 13 20 30 27 11 38 17 26 31 22 35 18 7 33 34 32 2 10 4 12 Mary-Beth: 3 27 0 36 14 18 17 34 20 5 35 1 26 6 32 37 7 4 29 23 2 25 13 11 END