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:
Finding Max/Min of a List or Collection
Java Program to Describe the Representation of Graph using Incidence Matrix
Partition a List in Java
Spring MVC Custom Validation
Truyền giá trị và tham chiếu trong java
Jackson – Marshall String to JsonNode
A Guide to JUnit 5 Extensions
Java Program to Implement Hash Tables Chaining with Binary Trees
Static Content in Spring WebFlux
Java Program to Construct an Expression Tree for an Postfix Expression
Giới thiệu Google Guice – Dependency injection (DI) framework
Java Program to Generate Random Numbers Using Multiply with Carry Method
Java Program to Implement Double Order Traversal of a Binary Tree
Loại bỏ các phần tử trùng trong một ArrayList như thế nào?
Java Program to Implement Circular Singly Linked List
Java Program to implement Bi Directional Map
Java Program to Implement LinkedTransferQueue API
Server-Sent Events in Spring
Java Program to Implement PriorityQueue API
Quick Intro to Spring Cloud Configuration
Converting Between Byte Arrays and Hexadecimal Strings in Java
Spring Cloud Bus
Java Program to Implement the Monoalphabetic Cypher
Spring REST API + OAuth2 + Angular
List Interface trong Java
Overview of the java.util.concurrent
Tính trừu tượng (Abstraction) trong Java
ClassNotFoundException vs NoClassDefFoundError
HashSet trong Java hoạt động như thế nào?
Java – Reader to String
Java Program to Show the Duality Transformation of Line and Point
Java Program to Implement WeakHashMap API