Java Program to Implement Gale Shapley Algorithm

This is a Java Program to Implement Gale Shapley Algorithm. Gale Shapley Algorithm is used to solve the stable marriage problem (SMP). SMP is the problem of finding a stable matching between two sets of elements given a set of preferences for each element.

Algorithm is as follows :

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked such woman to whom he has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}

Here is the source code of the Java Program to Implement Gale Shapley Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  *    Java Program to Implement Gale Shapley Algorithm 
  3.  **/
  4.  
  5. /** Class GaleShapley **/
  6. public class GaleShapley
  7. {
  8.     private int N, engagedCount;
  9.     private String[][] menPref;
  10.     private String[][] womenPref;
  11.     private String[] men;
  12.     private String[] women;
  13.     private String[] womenPartner;
  14.     private boolean[] menEngaged;
  15.  
  16.     /** Constructor **/
  17.     public GaleShapley(String[] m, String[] w, String[][] mp, String[][] wp)
  18.     {
  19.         N = mp.length;
  20.         engagedCount = 0;
  21.         men = m;
  22.         women = w;
  23.         menPref = mp;
  24.         womenPref = wp;
  25.         menEngaged = new boolean[N];
  26.         womenPartner = new String[N];
  27.         calcMatches();
  28.     }
  29.     /** function to calculate all matches **/
  30.     private void calcMatches()
  31.     {
  32.         while (engagedCount < N)
  33.         {
  34.             int free;
  35.             for (free = 0; free < N; free++)
  36.                 if (!menEngaged[free])
  37.                     break;
  38.  
  39.             for (int i = 0; i < N && !menEngaged[free]; i++)
  40.             {
  41.                 int index = womenIndexOf(menPref[free][i]);
  42.                 if (womenPartner[index] == null)
  43.                 {
  44.                     womenPartner[index] = men[free];
  45.                     menEngaged[free] = true;
  46.                     engagedCount++;
  47.                 }
  48.                 else
  49.                 {
  50.                     String currentPartner = womenPartner[index];
  51.                     if (morePreference(currentPartner, men[free], index))
  52.                     {
  53.                         womenPartner[index] = men[free];
  54.                         menEngaged[free] = true;
  55.                         menEngaged[menIndexOf(currentPartner)] = false;
  56.                     }
  57.                 }
  58.             }            
  59.         }
  60.         printCouples();
  61.     }
  62.     /** function to check if women prefers new partner over old assigned partner **/
  63.     private boolean morePreference(String curPartner, String newPartner, int index)
  64.     {
  65.         for (int i = 0; i < N; i++)
  66.         {
  67.             if (womenPref[index][i].equals(newPartner))
  68.                 return true;
  69.             if (womenPref[index][i].equals(curPartner))
  70.                 return false;
  71.         }
  72.         return false;
  73.     }
  74.     /** get men index **/
  75.     private int menIndexOf(String str)
  76.     {
  77.         for (int i = 0; i < N; i++)
  78.             if (men[i].equals(str))
  79.                 return i;
  80.         return -1;
  81.     }
  82.     /** get women index **/
  83.     private int womenIndexOf(String str)
  84.     {
  85.         for (int i = 0; i < N; i++)
  86.             if (women[i].equals(str))
  87.                 return i;
  88.         return -1;
  89.     }
  90.     /** print couples **/
  91.     public void printCouples()
  92.     {
  93.         System.out.println("Couples are : ");
  94.         for (int i = 0; i < N; i++)
  95.         {
  96.             System.out.println(womenPartner[i] +" "+ women[i]);
  97.         }
  98.     }
  99.     /** main function **/
  100.     public static void main(String[] args) 
  101.     {
  102.         System.out.println("Gale Shapley Marriage Algorithm\n");
  103.         /** list of men **/
  104.         String[] m = {"M1", "M2", "M3", "M4", "M5"};
  105.         /** list of women **/
  106.         String[] w = {"W1", "W2", "W3", "W4", "W5"};
  107.  
  108.         /** men preference **/
  109.         String[][] mp = {{"W5", "W2", "W3", "W4", "W1"}, 
  110.                          {"W2", "W5", "W1", "W3", "W4"}, 
  111.                          {"W4", "W3", "W2", "W1", "W5"}, 
  112.                          {"W1", "W2", "W3", "W4", "W5"},
  113.                          {"W5", "W2", "W3", "W4", "W1"}};
  114.         /** women preference **/                      
  115.         String[][] wp = {{"M5", "M3", "M4", "M1", "M2"}, 
  116.                          {"M1", "M2", "M3", "M5", "M4"}, 
  117.                          {"M4", "M5", "M3", "M2", "M1"},
  118.                          {"M5", "M2", "M1", "M4", "M3"}, 
  119.                          {"M2", "M1", "M4", "M3", "M5"}};
  120.  
  121.         GaleShapley gs = new GaleShapley(m, w, mp, wp);                        
  122.     }
  123. }

advertisement
advertisement
Gale Shapley Marriage Algorithm
 
Couples are :
M4 W1
M2 W2
M5 W3
M3 W4
M1 W5

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

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.