Repository: TheAlgorithms/Java
Pull request #5494 (2024-10-01 10:55:29)

Gale-Shapley Algorithm and Tests
Overview:
This pull request adds the implementation of the Gale-Shapley algorithm (Stable Marriage Problem) to the greedyalgorithms package. The algorithm allows for finding stable matches between two sets (men and women) based on their preferences. In addition to the algorithm, unit tests have been added to ensure correctness, and the DIRECTORY.md file has been updated to reflect this new addition.

Changes:
New Algorithm: Gale-Shapley algorithm for stable matching.
Unit Tests: JUnit tests added to validate the correctness of the Gale-Shapley algorithm with various scenarios, including multiple preferences, single pair matching, and equal preferences.
Directory Update: Updated DIRECTORY.md to include the new Gale-Shapley algorithm under the greedyalgorithms section.
Checklist:

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5494?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `81.25000%` with `3 lines` in your changes missing coverage. Please review.
> Project coverage is 52.32%. Comparing base [(`7f60d57`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/7f60d57504ab8456b72057735a0dc93595ad847f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`0e4ddcd`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/0e4ddcd9e35f5fc8d9818c7af08aff33b290fa5d?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5494?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...om/thealgorithms/greedyalgorithms/GaleShapley.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5494?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fgreedyalgorithms%2FGaleShapley.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9ncmVlZHlhbGdvcml0aG1zL0dhbGVTaGFwbGV5LmphdmE=) | 81.25% | [2 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5494?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5494      +/-   ##
============================================
+ Coverage     52.28%   52.32%   +0.03%     
- Complexity     3256     3260       +4     
============================================
  Files           525      526       +1     
  Lines         15185    15201      +16     
  Branches       2887     2890       +3     
============================================
+ Hits           7940     7954      +14     
- Misses         6920     6922       +2     
  Partials        325      325              
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5494?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 0e96e8fb..ee09790e 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -265,6 +265,7 @@
             * [ActivitySelection](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/ActivitySelection.java)
             * [CoinChange](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/CoinChange.java)
             * [FractionalKnapsack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/FractionalKnapsack.java)
+            * [GaleShapley](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/GaleShapley.java)
             * [JobSequencing](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/JobSequencing.java)
             * [MinimizingLateness](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/MinimizingLateness.java)
           * io
@@ -749,6 +750,7 @@
             * [ActivitySelectionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/ActivitySelectionTest.java)
             * [CoinChangeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/CoinChangeTest.java)
             * [FractionalKnapsackTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/FractionalKnapsackTest.java)
+            * [GaleShapleyTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/GaleShapleyTest.java)
             * [JobSequencingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/JobSequencingTest.java)
             * [MinimizingLatenessTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/MinimizingLatenessTest.java)
           * io
diff --git a/src/main/java/com/thealgorithms/greedyalgorithms/GaleShapley.java b/src/main/java/com/thealgorithms/greedyalgorithms/GaleShapley.java
new file mode 100644
index 00000000..a4a03663
--- /dev/null
+++ b/src/main/java/com/thealgorithms/greedyalgorithms/GaleShapley.java
@@ -0,0 +1,65 @@
+package com.thealgorithms.greedyalgorithms;
+
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.Map;
+
+/**
+ * Implementation of the Gale-Shapley Algorithm for Stable Matching.
+ * Problem link: https://en.wikipedia.org/wiki/Stable_marriage_problem
+ */
+public final class GaleShapley {
+
+    private GaleShapley() {
+    }
+
+    /**
+     * Function to find stable matches between men and women.
+     *
+     * @param womenPrefs A map containing women's preferences where each key is a woman and the value is an array of men in order of preference.
+     * @param menPrefs   A map containing men's preferences where each key is a man and the value is an array of women in order of preference.
+     * @return A map containing stable matches where the key is a woman and the value is her matched man.
+     */
+    public static Map<String, String> stableMatch(Map<String, LinkedList<String>> womenPrefs, Map<String, LinkedList<String>> menPrefs) {
+        // Initialize all men as free
+        Map<String, String> engagements = new HashMap<>();
+        LinkedList<String> freeMen = new LinkedList<>(menPrefs.keySet());
+
+        // While there are free men
+        while (!freeMen.isEmpty()) {
+            String man = freeMen.poll(); // Get the first free man
+            LinkedList<String> manPref = menPrefs.get(man); // Get the preferences of the man
+
+            // Check if manPref is null or empty
+            if (manPref == null || manPref.isEmpty()) {
+                continue; // Skip if no preferences
+            }
+
+            // Propose to the first woman in the man's preference list
+            String woman = manPref.poll();
+            String fiance = engagements.get(woman);
+
+            // If the woman is not engaged, engage her with the current man
+            if (fiance == null) {
+                engagements.put(woman, man);
+            } else {
+                // If the woman prefers the current man over her current fiance
+                LinkedList<String> womanPrefList = womenPrefs.get(woman);
+
+                // Check if womanPrefList is null
+                if (womanPrefList == null) {
+                    continue; // Skip if no preferences for the woman
+                }
+
+                if (womanPrefList.indexOf(man) < womanPrefList.indexOf(fiance)) {
+                    engagements.put(woman, man);
+                    freeMen.add(fiance); // Previous fiance becomes free
+                } else {
+                    // Woman rejects the new proposal, the man remains free
+                    freeMen.add(man);
+                }
+            }
+        }
+        return engagements; // Return the stable matches
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/greedyalgorithms/GaleShapleyTest.java b/src/test/java/com/thealgorithms/greedyalgorithms/GaleShapleyTest.java
new file mode 100644
index 00000000..fcd17320
--- /dev/null
+++ b/src/test/java/com/thealgorithms/greedyalgorithms/GaleShapleyTest.java
@@ -0,0 +1,72 @@
+package com.thealgorithms.greedyalgorithms;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import org.junit.jupiter.api.Test;
+
+public class GaleShapleyTest {
+
+    @Test
+    public void testStableMatch() {
+        Map<String, LinkedList<String>> womenPrefs = new HashMap<>();
+        womenPrefs.put("A", new LinkedList<>(List.of("X", "Y", "Z")));
+        womenPrefs.put("B", new LinkedList<>(List.of("Y", "X", "Z")));
+        womenPrefs.put("C", new LinkedList<>(List.of("X", "Y", "Z")));
+
+        Map<String, LinkedList<String>> menPrefs = new HashMap<>();
+        menPrefs.put("X", new LinkedList<>(List.of("A", "B", "C")));
+        menPrefs.put("Y", new LinkedList<>(List.of("B", "A", "C")));
+        menPrefs.put("Z", new LinkedList<>(List.of("A", "B", "C")));
+
+        Map<String, String> result = GaleShapley.stableMatch(womenPrefs, menPrefs);
+
+        Map<String, String> expected = new HashMap<>();
+        expected.put("A", "X");
+        expected.put("B", "Y");
+        expected.put("C", "Z");
+
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testSinglePair() {
+        Map<String, LinkedList<String>> womenPrefs = new HashMap<>();
+        womenPrefs.put("A", new LinkedList<>(List.of("X")));
+
+        Map<String, LinkedList<String>> menPrefs = new HashMap<>();
+        menPrefs.put("X", new LinkedList<>(List.of("A")));
+
+        Map<String, String> result = GaleShapley.stableMatch(womenPrefs, menPrefs);
+
+        Map<String, String> expected = new HashMap<>();
+        expected.put("A", "X");
+
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testEqualPreferences() {
+        Map<String, LinkedList<String>> womenPrefs = new HashMap<>();
+        womenPrefs.put("A", new LinkedList<>(List.of("X", "Y", "Z")));
+        womenPrefs.put("B", new LinkedList<>(List.of("X", "Y", "Z")));
+        womenPrefs.put("C", new LinkedList<>(List.of("X", "Y", "Z")));
+
+        Map<String, LinkedList<String>> menPrefs = new HashMap<>();
+        menPrefs.put("X", new LinkedList<>(List.of("A", "B", "C")));
+        menPrefs.put("Y", new LinkedList<>(List.of("A", "B", "C")));
+        menPrefs.put("Z", new LinkedList<>(List.of("A", "B", "C")));
+
+        Map<String, String> result = GaleShapley.stableMatch(womenPrefs, menPrefs);
+
+        Map<String, String> expected = new HashMap<>();
+        expected.put("A", "X");
+        expected.put("B", "Y");
+        expected.put("C", "Z");
+
+        assertEquals(expected, result);
+    }
+}