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:
Java Concurrency Interview Questions and Answers
Java Perform to a 2D FFT Inplace Given a Complex 2D Array
Introduction to Spliterator in Java
Spring Security Registration – Resend Verification Email
Guide to BufferedReader
Java Program to Implement Slicker Algorithm that avoids Triangulation to Find Area of a Polygon
An Introduction to Java.util.Hashtable Class
Hướng dẫn Java Design Pattern – Interpreter
Spring Boot - Logging
Spring Boot - Zuul Proxy Server and Routing
Write/Read cookies using HTTP and Read a file from the internet
Java Program to Perform Insertion in a 2 Dimension K-D Tree
Java 8 Stream API Analogies in Kotlin
Mix plain text and HTML content in a mail
Java Program to implement Sparse Vector
Spring RestTemplate Request/Response Logging
Spring Boot Actuator
Spring Boot - Google OAuth2 Sign-In
Java Program to Perform Matrix Multiplication
Java Program to Find Transitive Closure of a Graph
Map Interface trong java
Xử lý ngoại lệ trong Java (Exception Handling)
Spring Boot - Tomcat Port Number
Quick Intro to Spring Cloud Configuration
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Guide to Java 8’s Collectors
How to Get a Name of a Method Being Executed?
Java Program to Implement Bresenham Line Algorithm
Java Program to Implement Suffix Tree
Hướng dẫn kết nối cơ sở dữ liệu với Java JDBC
Java Program to Perform Searching Using Self-Organizing Lists
Binary Numbers in Java