Problema de matrimonio estable

El Problema del Matrimonio Estable establece que dados N hombres y N mujeres, donde cada persona ha clasificado a todos los miembros del sexo opuesto en orden de preferencia, casar a los hombres y mujeres juntos de tal manera que no haya dos personas del sexo opuesto que prefieran tener ambos. entre sí que sus parejas actuales. Si no hay tales personas, todos los matrimonios son «estables» (Fuente Wiki ).

Considere el siguiente ejemplo.
Sean dos hombres m1 y m2 y dos mujeres w1 y w2.
Sea la lista de preferencias de m1 {w1, w2} 
Sea la lista de preferencias de m2 {w1, w2} 
Sea la lista de preferencias de w1 {m1, m2} 
Sea {m1, m2} la lista de preferencias de w2

La coincidencia { {m1, w2}, {w1, m2} } no es estable porque m1 y w1 se preferirían entre sí sobre sus socios asignados.
La coincidencia {m1, w1} y {m2, w2} es estable porque no hay dos personas de sexo opuesto que se prefieran
a sus parejas asignadas.

Siempre es posible formar matrimonios estables a partir de listas de preferencias (Ver referencias para la prueba). El siguiente es el algoritmo de Gale-Shapley para encontrar una coincidencia estable: 
la idea es iterar a través de todos los hombres libres mientras haya algún hombre libre disponible. Cada hombre libre va a todas las mujeres en su lista de preferencias según el orden. Por cada mujer a la que acude, comprueba si la mujer está libre, si es así, ambos se comprometen. Si la mujer no es libre, entonces la mujer elige decirle que no o abandonar su compromiso actual de acuerdo con su lista de preferencias. Entonces, un compromiso hecho una vez puede romperse si una mujer obtiene una mejor opción. La complejidad temporal del algoritmo de Gale-Shapley es O(n ² ). 

Initialize all men and women to free
while there exist a 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    
}

Entrada y Salida: La entrada es una array 2D de tamaño (2*N)*N donde N es el número de mujeres u hombres. Las filas de 0 a N-1 representan listas de preferencias de hombres y las filas de N a 2*N – 1 representan listas de preferencias de mujeres. Entonces, los hombres se numeran de 0 a N-1 y las mujeres se numeran de N a 2*N – 1. El resultado es una lista de parejas casadas. 

A continuación se muestra la implementación del algoritmo anterior.  

C++

// C++ program for stable marriage problem #include <iostream> #include <string.h> #include <stdio.h> using namespace std;    // Number of Men or Women #define N  4    // This function returns true if woman 'w' prefers man 'm1' over man 'm' bool wPrefersM1OverM(int prefer[2*N][N], int w, int m, int m1) {     // Check if w prefers m over her current engagement m1     for (int i = 0; i < N; i++)     {         // If m1 comes before m in list of w, then w prefers her         // current engagement, don't do anything         if (prefer[w][i] == m1)             return true;            // If m comes before m1 in w's list, then free her current         // engagement and engage her with m         if (prefer[w][i] == m)            return false;     } }    // Prints stable matching for N boys and N girls. // Boys are numbered as 0 to N-1. Girls are numbered  // as N to 2N-1. void stableMarriage(int prefer[2*N][N]) {     // Stores partner of women. This is our output array that     // stores passing 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[N];        // An array to store availability of men.  If mFree[i] is     // false, then man 'i' is free, otherwise engaged.     bool mFree[N];        // Initialize all men and women as free     memset(wPartner, -1, sizeof(wPartner));     memset(mFree, false, sizeof(mFree));     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     cout << "Woman   Man" << endl;     for (int i = 0; i < N; i++)        cout << " " << i+N << "\t" << wPartner[i] << endl; }    // Driver program to test above functions int main() {     int prefer[2*N][N] = { {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);        return 0; }

Java

// Java program for stable marriage problem  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 engagement m1      for (int i = 0; i < N; i++)      {          // If m1 comes before m in list of w,          // then w prefers her current engagement,         // don't do anything          if (prefer[w][i] == m1)              return true;             // If m comes 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 numbered as N to 2N-1.  static void stableMarriage(int prefer[][])  {      // Stores partner of women. This is our     // output array that stores passing 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

Python3

# Python3 program for stable marriage problem    # Number of Men or Women N = 4    # This function returns true if  # woman 'w' prefers man 'm1' over man 'm' def wPrefersM1OverM(prefer, w, m, m1):            # Check if w prefers m over her      # current engagement m1     for i in range(N):                    # If m1 comes before m in list of w,          # then w prefers her current engagement,         # don't do anything         if (prefer[w][i] == m1):             return True            # If m comes before m1 in w's list,          # then free her current engagement          # and engage her with m         if (prefer[w][i] == m):             return False    # Prints stable matching for N boys and N girls.  # Boys are numbered as 0 to N-1.  # Girls are numbered as N to 2N-1. def stableMarriage(prefer):            # Stores partner of women. This is our output      # array that stores passing 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     wPartner = [-1 for i in range(N)]        # An array to store availability of men.      # If mFree[i] is false, then man 'i' is free,     # otherwise engaged.     mFree = [False for i in range(N)]        freeCount = N        # While there are free men     while (freeCount > 0):                    # Pick the first free man (we could pick any)         m = 0         while (m < N):             if (mFree[m] == False):                 break             m += 1            # One by one go to all women according to          # m's preferences. Here m is the picked free man         i = 0         while i < N and mFree[m] == False:             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 -= 1                else:                                     # If w is not free                 # Find current engagement of w                 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             i += 1                # End of Else         # End of the for loop that goes          # to all women in m's list     # End of main while loop        # Print solution     print("Woman ", " Man")     for i in range(N):         print(i + N, "\t", wPartner[i])    # Driver Code prefer = [[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 Mohit Kumar

C#

// C# program for stable marriage problem  using System; using System.Collections.Generic;    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 bool wPrefersM1OverM(int [,]prefer, int w,                              int m, int m1)  {      // Check if w prefers m over      // her current engagement m1      for (int i = 0; i < N; i++)      {          // If m1 comes before m in list of w,          // then w prefers her current engagement,          // don't do anything          if (prefer[w, i] == m1)              return true;             // If m comes 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 numbered as N to 2N-1.  static void stableMarriage(int [,]prefer)  {      // Stores partner of women. This is our      // output array that stores passing 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.      bool []mFree = new bool[N];         // Initialize all men and women as free      for (int i = 0; i < N; i++)          wPartner[i] = -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      Console.WriteLine("Woman Man");      for (int i = 0; i < N; i++)      {          Console.Write(" ");          Console.WriteLine(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 Rajput-Ji

JavaScript

<script> // Javascript program for stable marriage problem    // Number of Men or Women N = 4;    // This function returns true if woman 'w' prefers man 'm1' over man 'm' function wPrefersM1OverM( prefer,  w,  m,  m1) {        // Check if w prefers m over her current engagement m1     for (var i = 0; i < N; i++)     {                // If m1 comes before m in list of w, then w prefers her         // current engagement, don't do anything         if (prefer[w][i] == m1)             return true;            // If m comes before m1 in w's list, then free her current         // engagement and engage her with m         if (prefer[w][i] == m)            return false;     } }    // Prints stable matching for N boys and N girls. Boys are numbered as 0 to // N-1. Girls are numbered as N to 2N-1. function stableMarriage( prefer) {        // Stores partner of women. This is our output array that     // stores passing 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     var wPartner = new Array(N);        // An array to store availability of men.  If mFree[i] is     // false, then man 'i' is free, otherwise engaged.      mFree = new Array(N);        // Initialize all men and women as free     wPartner.fill(-1);     mFree.fill(false);     var freeCount = N;        // While there are free men     while (freeCount > 0)     {         // Pick the first free man (we could pick any)         var 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 (var i = 0; i < N && mFree[m] == false; i++)         {             var 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                 var 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      document.write("Woman      Man" +"<br>");     for (var i = 0; i < N; i++)       document.write(" " + (i+N) + "     " + wPartner[i] +"<br>"); }    var prefer  = [ [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 SoumikMondal </script>

Producción

Woman   Man
 4    2
 5    1
 6    3
 7    0