Java Program to Implement Stable Marriage Problem

This is a java program to solve a matching problem for stable marriage matching problem. In mathematics, economics, and computer science, the stable marriage problem (SMP) is the problem of finding a stable matching between two sets of elements given a set of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is stable whenever it is not the case that both:

1. some given element A of the first matched set prefers some given element B of the second matched set over the element to which A is already matched, and
2. B also prefers A over the element to which B is already matched

In other words, a matching is stable when there does not exist any alternative pairing (A, B) in which both A and B are individually better off than they would be with the element to which they are currently matched.

The stable marriage problem is commonly stated as:
Given n men and n women, where each person has ranked all members of the opposite gender with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite gender who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”.

Here is the source code of the Java Program to Solve a Matching Problem for a Given Specific Case. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.graph;
  3.  
  4. import java.util.*;
  5.  
  6. public class MatchingProblemStableMarriage
  7. {
  8.     static List<String> guys = Arrays.asList(new String[] { "abe", "bob",
  9.             "col", "dan", "ed", "fred", "gav", "hal", "ian", "jon" });
  10.     static List<String> girls = Arrays.asList(new String[] { "abi", "bea",
  11.             "cath", "dee", "eve", "fay", "gay", "hope", "ivy", "jan" });
  12.     static Map<String, List<String>> guyPrefers = new HashMap<String, List<String>>()
  13.     {
  14.         private static final long serialVersionUID = 1L;
  15.         {
  16.             put("abe", Arrays.asList("abi", "eve", "cath", "ivy", "jan", "dee",
  17.                     "fay", "bea", "hope", "gay"));
  18.             put("bob", Arrays.asList("cath", "hope", "abi", "dee", "eve",
  19.                     "fay", "bea", "jan", "ivy", "gay"));
  20.             put("col", Arrays.asList("hope", "eve", "abi", "dee", "bea", "fay",
  21.                     "ivy", "gay", "cath", "jan"));
  22.             put("dan", Arrays.asList("ivy", "fay", "dee", "gay", "hope", "eve",
  23.                     "jan", "bea", "cath", "abi"));
  24.             put("ed", Arrays.asList("jan", "dee", "bea", "cath", "fay", "eve",
  25.                     "abi", "ivy", "hope", "gay"));
  26.             put("fred", Arrays.asList("bea", "abi", "dee", "gay", "eve", "ivy",
  27.                     "cath", "jan", "hope", "fay"));
  28.             put("gav", Arrays.asList("gay", "eve", "ivy", "bea", "cath", "abi",
  29.                     "dee", "hope", "jan", "fay"));
  30.             put("hal", Arrays.asList("abi", "eve", "hope", "fay", "ivy",
  31.                     "cath", "jan", "bea", "gay", "dee"));
  32.             put("ian", Arrays.asList("hope", "cath", "dee", "gay", "bea",
  33.                     "abi", "fay", "ivy", "jan", "eve"));
  34.             put("jon", Arrays.asList("abi", "fay", "jan", "gay", "eve", "bea",
  35.                     "dee", "cath", "ivy", "hope"));
  36.         }
  37.     };
  38.     static Map<String, List<String>> girlPrefers = new HashMap<String, List<String>>()
  39.     {
  40.         private static final long serialVersionUID = 1L;
  41.         {
  42.             put("abi", Arrays.asList("bob", "fred", "jon", "gav", "ian", "abe",
  43.                     "dan", "ed", "col", "hal"));
  44.             put("bea", Arrays.asList("bob", "abe", "col", "fred", "gav", "dan",
  45.                     "ian", "ed", "jon", "hal"));
  46.             put("cath", Arrays.asList("fred", "bob", "ed", "gav", "hal", "col",
  47.                     "ian", "abe", "dan", "jon"));
  48.             put("dee", Arrays.asList("fred", "jon", "col", "abe", "ian", "hal",
  49.                     "gav", "dan", "bob", "ed"));
  50.             put("eve", Arrays.asList("jon", "hal", "fred", "dan", "abe", "gav",
  51.                     "col", "ed", "ian", "bob"));
  52.             put("fay", Arrays.asList("bob", "abe", "ed", "ian", "jon", "dan",
  53.                     "fred", "gav", "col", "hal"));
  54.             put("gay", Arrays.asList("jon", "gav", "hal", "fred", "bob", "abe",
  55.                     "col", "ed", "dan", "ian"));
  56.             put("hope", Arrays.asList("gav", "jon", "bob", "abe", "ian", "dan",
  57.                     "hal", "ed", "col", "fred"));
  58.             put("ivy", Arrays.asList("ian", "col", "hal", "gav", "fred", "bob",
  59.                     "abe", "ed", "jon", "dan"));
  60.             put("jan", Arrays.asList("ed", "hal", "gav", "abe", "bob", "jon",
  61.                     "col", "ian", "fred", "dan"));
  62.         }
  63.     };
  64.  
  65.     public static void main(String[] args)
  66.     {
  67.         Map<String, String> matches = match(guys, guyPrefers, girlPrefers);
  68.         for (Map.Entry<String, String> couple : matches.entrySet())
  69.         {
  70.             System.out.println(couple.getKey() + " is engaged to "
  71.                     + couple.getValue());
  72.         }
  73.         if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
  74.         {
  75.             System.out.println("Marriages are stable");
  76.         }
  77.         else
  78.         {
  79.             System.out.println("Marriages are unstable");
  80.         }
  81.         String tmp = matches.get(girls.get(0));
  82.         matches.put(girls.get(0), matches.get(girls.get(1)));
  83.         matches.put(girls.get(1), tmp);
  84.         System.out.println(girls.get(0) + " and " + girls.get(1)
  85.                 + " have switched partners");
  86.         if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
  87.         {
  88.             System.out.println("Marriages are stable");
  89.         }
  90.         else
  91.         {
  92.             System.out.println("Marriages are unstable");
  93.         }
  94.     }
  95.  
  96.     private static Map<String, String> match(List<String> guys,
  97.             Map<String, List<String>> guyPrefers,
  98.             Map<String, List<String>> girlPrefers)
  99.     {
  100.         Map<String, String> engagedTo = new TreeMap<String, String>();
  101.         List<String> freeGuys = new LinkedList<String>();
  102.         freeGuys.addAll(guys);
  103.         while (!freeGuys.isEmpty())
  104.         {
  105.             String thisGuy = freeGuys.remove(0); // get a load of THIS guy
  106.             List<String> thisGuyPrefers = guyPrefers.get(thisGuy);
  107.             for (String girl : thisGuyPrefers)
  108.             {
  109.                 if (engagedTo.get(girl) == null)
  110.                 {// girl is free
  111.                     engagedTo.put(girl, thisGuy); // awww
  112.                     break;
  113.                 }
  114.                 else
  115.                 {
  116.                     String otherGuy = engagedTo.get(girl);
  117.                     List<String> thisGirlPrefers = girlPrefers.get(girl);
  118.                     if (thisGirlPrefers.indexOf(thisGuy) < thisGirlPrefers
  119.                             .indexOf(otherGuy))
  120.                     {
  121.                         // this girl prefers this guy to the guy she's engaged
  122.                         // to
  123.                         engagedTo.put(girl, thisGuy);
  124.                         freeGuys.add(otherGuy);
  125.                         break;
  126.                     }// else no change...keep looking for this guy
  127.                 }
  128.             }
  129.         }
  130.         return engagedTo;
  131.     }
  132.  
  133.     private static boolean checkMatches(List<String> guys, List<String> girls,
  134.             Map<String, String> matches, Map<String, List<String>> guyPrefers,
  135.             Map<String, List<String>> girlPrefers)
  136.     {
  137.         if (!matches.keySet().containsAll(girls))
  138.         {
  139.             return false;
  140.         }
  141.         if (!matches.values().containsAll(guys))
  142.         {
  143.             return false;
  144.         }
  145.         Map<String, String> invertedMatches = new TreeMap<String, String>();
  146.         for (Map.Entry<String, String> couple : matches.entrySet())
  147.         {
  148.             invertedMatches.put(couple.getValue(), couple.getKey());
  149.         }
  150.         for (Map.Entry<String, String> couple : matches.entrySet())
  151.         {
  152.             List<String> shePrefers = girlPrefers.get(couple.getKey());
  153.             List<String> sheLikesBetter = new LinkedList<String>();
  154.             sheLikesBetter.addAll(shePrefers.subList(0,
  155.                     shePrefers.indexOf(couple.getValue())));
  156.             List<String> hePrefers = guyPrefers.get(couple.getValue());
  157.             List<String> heLikesBetter = new LinkedList<String>();
  158.             heLikesBetter.addAll(hePrefers.subList(0,
  159.                     hePrefers.indexOf(couple.getKey())));
  160.             for (String guy : sheLikesBetter)
  161.             {
  162.                 String guysFinace = invertedMatches.get(guy);
  163.                 List<String> thisGuyPrefers = guyPrefers.get(guy);
  164.                 if (thisGuyPrefers.indexOf(guysFinace) > thisGuyPrefers
  165.                         .indexOf(couple.getKey()))
  166.                 {
  167.                     System.out.printf("%s likes %s better than %s and %s"
  168.                             + " likes %s better than their current partner\n",
  169.                             couple.getKey(), guy, couple.getValue(), guy,
  170.                             couple.getKey());
  171.                     return false;
  172.                 }
  173.             }
  174.             for (String girl : heLikesBetter)
  175.             {
  176.                 String girlsFinace = matches.get(girl);
  177.                 List<String> thisGirlPrefers = girlPrefers.get(girl);
  178.                 if (thisGirlPrefers.indexOf(girlsFinace) > thisGirlPrefers
  179.                         .indexOf(couple.getValue()))
  180.                 {
  181.                     System.out.printf("%s likes %s better than %s and %s"
  182.                             + " likes %s better than their current partner\n",
  183.                             couple.getValue(), girl, couple.getKey(), girl,
  184.                             couple.getValue());
  185.                     return false;
  186.                 }
  187.             }
  188.         }
  189.         return true;
  190.     }
  191. }

Output:

advertisement
advertisement
$ javac MatchingProblemStableMarriage.java
$ java MatchingProblemStableMarriage
 
abi is engaged to jon
bea is engaged to fred
cath is engaged to bob
dee is engaged to col
eve is engaged to hal
fay is engaged to dan
gay is engaged to gav
hope is engaged to ian
ivy is engaged to abe
jan is engaged to ed
Marriages are stable
abi and bea have switched partners
fred likes bea better than abi and bea likes fred better than their current partner
Marriages are unstable

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.