# 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. `}`

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
```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.