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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

« Prev - Java Program to Implement Rabin-Karp Method for Pattern Searching

» Next - Java Program to Implement Boyer Moore Algorithm

Related Posts:

Recommended Articles: