daily pastebin goal
82%
SHARE
TWEET

StableMarriage

a guest May 16th, 2018 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.util.*;
  4.  
  5. public class StableMarriage
  6. {
  7.     public static void main(String[] args) throws FileNotFoundException
  8.     {
  9.         ArrayList<Person> men = importMen();
  10.         ArrayList<Person> women = importWomen();
  11.  
  12.         Map<Person, Person> pairings = determinePairs(men, women);
  13.         print(pairings);
  14.     }
  15.     public static ArrayList<Person> importMen() throws FileNotFoundException
  16.     {
  17.         Scanner boy = new Scanner(new File("Boys.txt"));
  18.         ArrayList<Person> men = new ArrayList<>(50);
  19.  
  20.         while(boy.hasNext())
  21.         {
  22.             String person = boy.next();
  23.             if(person.equals("END"))
  24.             {
  25.                 break;
  26.             }
  27.             String name = person.substring(0, person.indexOf(":"));
  28.  
  29.             ArrayList<Integer> preferences = new ArrayList<>(50);
  30.  
  31.             while(boy.hasNextInt())
  32.             {
  33.                 preferences.add(boy.nextInt());
  34.             }
  35.             preferences.trimToSize();
  36.             men.add(new Person(name, preferences));
  37.         }
  38.         men.trimToSize();
  39.         return men;
  40.     }
  41.     public static ArrayList<Person> importWomen() throws FileNotFoundException
  42.     {
  43.         Scanner girl = new Scanner(new File("Girls.txt"));
  44.         ArrayList<Person> women = new ArrayList<>(50);
  45.  
  46.         while(girl.hasNext())
  47.         {
  48.             String person = girl.next();
  49.             if(person.equals("END"))
  50.             {
  51.                 break;
  52.             }
  53.             String name = person.substring(0, person.indexOf(":"));
  54.  
  55.             ArrayList<Integer> preferences = new ArrayList<>();
  56.  
  57.             while(girl.hasNextInt())
  58.             {
  59.                 preferences.add(girl.nextInt());
  60.             }
  61.             preferences.trimToSize();
  62.             women.add(new Person(name, preferences));
  63.         }
  64.         women.trimToSize();
  65.         return women;
  66.     }
  67.     public static Map<Person, Person> determinePairs(ArrayList<Person> men, ArrayList<Person> women)
  68.     {
  69.         //set each person to be free
  70.         Map<Person, Person> pairings = new HashMap<>();
  71.  
  72.         //while(some women w with a nonempty preference is free)
  73.         while(pairings.size() < women.size())
  74.         {
  75.             for(int i = 0; i < women.size(); i++)
  76.             {
  77.                 Person w = women.get(i);
  78.                 while(w.getPreferences().size() > 0 && !pairings.containsKey(w))
  79.                 {
  80.                     //set m = first man on w's list
  81.                     int firstMan = w.getPreferences().get(0);
  82.                     Person m = men.get(firstMan);
  83.                     //set woman free if engaged to man m
  84.                     if(pairings.containsValue(m))
  85.                     {
  86.                         pairings.values().remove(m);
  87.                     }
  88.                     //set m and w to be engaged to each other
  89.                     pairings.put(w, m);
  90.                     //for each successor q of w on m's list
  91.                     int q = m.getPreferences().indexOf(i);
  92.  
  93.                     for(int j = m.getPreferences().size() - 1; j > q; j--)
  94.                     {
  95.                         Person womanToDelete = women.get(m.getPreferences().get(j));
  96.                         int manToDelete = womanToDelete.getPreferences().indexOf(firstMan);
  97.                         //delete m from q's preference list
  98.                         womanToDelete.getPreferences().remove(manToDelete);
  99.                         //delete q from m's preference list
  100.                         m.getPreferences().remove(j);
  101.                     }
  102.                 }
  103.             }
  104.         }
  105.         return pairings;
  106.     }
  107.  
  108.     public static void print(Map<Person, Person> pairings)
  109.     {
  110.         for(Map.Entry<Person, Person> pair: pairings.entrySet())
  111.         {
  112.             System.out.println(pair.getKey().getName() + " and " + pair.getValue().getName() + " are engaged.");
  113.         }
  114.     }
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top