Question

Write a concurrent program to solve stable marriage problem using Akka with Java. Be sure to explain your solution strategy Given n men and n women and a preference order of marriage from each one of them, how to marry these 2n bachelors such that their marriages are stable. A marriage is stable when both partners in a couple cannot find anyone else (higher in their priority list) available for marriage. In other words, a marriage is stable when every person gets its most desired partner subject to availability. Consider the following example Let there be two men ml and m2 and two women w1 and w2. Let ml's list of preferences be w, w2) Let m2's list of preferences be w, w2) Let wI's list of preferences be m, m2) Let w2's list of preferences be ml, m2) The matchingm, w2, (w, m2 is not stable because ml and wl would prefer each other over their assigned partners. The matching ml, w and (m2, w2) is stable because there are no two people of opposite sex that would prefer each other over their assigned partners.

Answer 1

import java.util.*;

class GFG
{

// Number of Men or Women
static int N = 4;

// This function returns true if woman
// 'w' prefers man 'm1' over man 'm'
static boolean wPrefersM1OverM(int prefer[][], int w,
                           int m, int m1)
{
   // Check if w prefers m over
   // her current engagment m1
   for (int i = 0; i < N; i++)
   {
       // If m1 comes before m in lisr of w,
       // then w prefers her current engagement,
       // don't do anything
       if (prefer[w][i] == m1)
           return true;

       // If m cmes before m1 in w's list,
       // then free her current engagement
       // and engage her with m
       if (prefer[w][i] == m)
       return false;
   }
   return false;
}

// Prints stable matching for N boys and
// N girls. Boys are numbered as 0 to
// N-1. Girls are numbereed as N to 2N-1.
static void stableMarriage(int prefer[][])
{
   // Stores partner of women. This is our
   // output array that stores paing information.
   // The value of wPartner[i] indicates the partner
   // assigned to woman N+i. Note that the woman
   // numbers between N and 2*N-1. The value -1
   // indicates that (N+i)'th woman is free
   int wPartner[] = new int[N];

   // An array to store availability of men.
   // If mFree[i] is false, then man 'i' is
   // free, otherwise engaged.
   boolean mFree[] = new boolean[N];

   // Initialize all men and women as free
   Arrays.fill(wPartner, -1);
   int freeCount = N;

   // While there are free men
   while (freeCount > 0)
   {
       // Pick the first free man
       // (we could pick any)
       int m;
       for (m = 0; m < N; m++)
           if (mFree[m] == false)
               break;

       // One by one go to all women
       // according to m's preferences.
       // Here m is the picked free man
       for (int i = 0; i < N &&
                       mFree[m] == false; i++)
       {
           int w = prefer[m][i];

           // The woman of preference is free,
           // w and m become partners (Note that
           // the partnership maybe changed later).
           // So we can say they are engaged not married
           if (wPartner[w - N] == -1)
           {
               wPartner[w - N] = m;
               mFree[m] = true;
               freeCount--;
           }

           else // If w is not free
           {
               // Find current engagement of w
               int m1 = wPartner[w - N];

               // If w prefers m over her current engagement m1,
               // then break the engagement between w and m1 and
               // engage m with w.
               if (wPrefersM1OverM(prefer, w, m, m1) == false)
               {
                   wPartner[w - N] = m;
                   mFree[m] = true;
                   mFree[m1] = false;
               }
           } // End of Else
       } // End of the for loop that goes
       // to all women in m's list
   } // End of main while loop

// Print the solution
System.out.println("Woman Man");
for (int i = 0; i < N; i++)
{
   System.out.print(" ");
   System.out.println(i + N + "   " +
                       wPartner[i]);
}
}

// Driver Code
public static void main(String[] args)
{
   int prefer[][] = new int[][]{{7, 5, 6, 4},
                               {5, 4, 6, 7},
                               {4, 5, 6, 7},
                               {4, 5, 6, 7},
                               {0, 1, 2, 3},
                               {0, 1, 2, 3},
                               {0, 1, 2, 3},
                               {0, 1, 2, 3}};
   stableMarriage(prefer);
}
}

// This code is contributed by Prerna Saini