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.

/**
 *    Java Program to Implement Gale Shapley Algorithm 
 **/
 
/** Class GaleShapley **/
public class GaleShapley
{
    private int N, engagedCount;
    private String[][] menPref;
    private String[][] womenPref;
    private String[] men;
    private String[] women;
    private String[] womenPartner;
    private boolean[] menEngaged;
 
    /** Constructor **/
    public GaleShapley(String[] m, String[] w, String[][] mp, String[][] wp)
    {
        N = mp.length;
        engagedCount = 0;
        men = m;
        women = w;
        menPref = mp;
        womenPref = wp;
        menEngaged = new boolean[N];
        womenPartner = new String[N];
        calcMatches();
    }
    /** function to calculate all matches **/
    private void calcMatches()
    {
        while (engagedCount < N)
        {
            int free;
            for (free = 0; free < N; free++)
                if (!menEngaged[free])
                    break;
 
            for (int i = 0; i < N && !menEngaged[free]; i++)
            {
                int index = womenIndexOf(menPref[free][i]);
                if (womenPartner[index] == null)
                {
                    womenPartner[index] = men[free];
                    menEngaged[free] = true;
                    engagedCount++;
                }
                else
                {
                    String currentPartner = womenPartner[index];
                    if (morePreference(currentPartner, men[free], index))
                    {
                        womenPartner[index] = men[free];
                        menEngaged[free] = true;
                        menEngaged[menIndexOf(currentPartner)] = false;
                    }
                }
            }            
        }
        printCouples();
    }
    /** function to check if women prefers new partner over old assigned partner **/
    private boolean morePreference(String curPartner, String newPartner, int index)
    {
        for (int i = 0; i < N; i++)
        {
            if (womenPref[index][i].equals(newPartner))
                return true;
            if (womenPref[index][i].equals(curPartner))
                return false;
        }
        return false;
    }
    /** get men index **/
    private int menIndexOf(String str)
    {
        for (int i = 0; i < N; i++)
            if (men[i].equals(str))
                return i;
        return -1;
    }
    /** get women index **/
    private int womenIndexOf(String str)
    {
        for (int i = 0; i < N; i++)
            if (women[i].equals(str))
                return i;
        return -1;
    }
    /** print couples **/
    public void printCouples()
    {
        System.out.println("Couples are : ");
        for (int i = 0; i < N; i++)
        {
            System.out.println(womenPartner[i] +" "+ women[i]);
        }
    }
    /** main function **/
    public static void main(String[] args) 
    {
        System.out.println("Gale Shapley Marriage Algorithm\n");
        /** list of men **/
        String[] m = {"M1", "M2", "M3", "M4", "M5"};
        /** list of women **/
        String[] w = {"W1", "W2", "W3", "W4", "W5"};
 
        /** men preference **/
        String[][] mp = {{"W5", "W2", "W3", "W4", "W1"}, 
                         {"W2", "W5", "W1", "W3", "W4"}, 
                         {"W4", "W3", "W2", "W1", "W5"}, 
                         {"W1", "W2", "W3", "W4", "W5"},
                         {"W5", "W2", "W3", "W4", "W1"}};
        /** women preference **/                      
        String[][] wp = {{"M5", "M3", "M4", "M1", "M2"}, 
                         {"M1", "M2", "M3", "M5", "M4"}, 
                         {"M4", "M5", "M3", "M2", "M1"},
                         {"M5", "M2", "M1", "M4", "M3"}, 
                         {"M2", "M1", "M4", "M3", "M5"}};
 
        GaleShapley gs = new GaleShapley(m, w, mp, wp);                        
    }
}

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

Related posts:

Spring Boot Change Context Path
Lập trình đa luồng với CompletableFuture trong Java 8
Java Program to Check whether Graph is a Bipartite using BFS
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
The Modulo Operator in Java
Java Program to Implement Wagner and Fisher Algorithm for online String Matching
How to Set TLS Version in Apache HttpClient
Spring Boot - Google Cloud Platform
Java Program to Implement Control Table
Java Program to Implement Attribute API
Chuyển đổi từ HashMap sang ArrayList
Hướng dẫn sử dụng Java String, StringBuffer và StringBuilder
The Order of Tests in JUnit
Java Program to Generate Random Numbers Using Middle Square Method
Using the Map.Entry Java Class
Java Program to Implement Circular Doubly Linked List
Handling URL Encoded Form Data in Spring REST
Spring REST with a Zuul Proxy
Request a Delivery / Read Receipt in Javamail
Integer Constant Pool trong Java
Java Program to Implement Quick sort
Guide to the Volatile Keyword in Java
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Java Program to Implement Borwein Algorithm
Java Program to Perform Partial Key Search in a K-D Tree
Tính trừu tượng (Abstraction) trong Java
Spring Security and OpenID Connect
Java Program to Implement Sieve Of Sundaram
Spring Boot - Tracing Micro Service Logs
Tiêu chuẩn coding trong Java (Coding Standards)
Java Program to Implement Ternary Heap