Stable Married Couple Problem
There are two groups of men and women who desire to get married. Participants of each group indicate who among the opposite sex would be acceptable as a potential spouse. Every woman can be married to at most one man, and every man to at most one woman.
To solve this problem, we used set of input data for equal number of men and women, where each person has an ordered list of preferences for whom that person would like to marry. Task is to pair up the man with the woman in such a way that no one is unsatisfied with their partner. There we used bipartite graph implementation through the adjacency matrix and BFS algorithm to pair up (married couple) men and women and repeatedly improve the pairings as necessary until every person is satisfied.
Consider an engagement (m, w) between man m and woman w. It says that (m, w) is unstable if either m or w has another person they would rather marry. It means unstable engagement meets one or more of the following condition. (Following matching sequence steps called Gale-shape Algorithm).
- There is another woman w2 such that m and w2 both prefer each other to their current partners, that is m prefers the pair (m, w2) to (m, w) and w2 is either single or engage to a man she likes less than m or
- There is another man m2 such that m2 and w both prefer each other to their current partners, that is w prefers the pair (m2, w) to (m, w) and m2 is either single or engage to a woman he likes less than w.
Here we used adjacency matrix to represent the preference order of each man and woman and used separate queue for hold all the unmarried set of men (m1, m2, m3, m4). This initial state should input to the algorithm.
Implementation in C#
StableMarrage.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace StableMarriedcouplewithBFS
{
class StableMarrage
{
//Adjacancy matrices for disjoint sets mapping
private int[][] manpreference;//Store the Preference table of men
private int[][] womanpreference;//Store the Preference table of woman
private int numofcouple;//Store the number of couples
//private static readonly bool value = false;
private Random rnd = new Random();//Random function generator
static void Main(string[] args)
{
//Two disjoint sets manlist and womanlist
string[] manlist = { "George", "Jerry", "Dinesh", "Sachin" };
string[] womanlist = { "Carine", "Leela", "Kamala", "Jane" };
int numofcouple = manlist.Length;
StableMarrage couple = new StableMarrage(numofcouple);//Checking stable marrages
couple.showPreftable(manlist, womanlist);//Show the preference tables
int[] marriedCouple = couple.stableCouple();//Take the married couples
couple.showMarriagecouples(marriedCouple, manlist, womanlist);//Show married couples on the console
Console.ReadKey();
}
//Create the random preferences for each men and women list
public StableMarrage(int lenth)
{
this.numofcouple = lenth;
manpreference = new int[lenth][];
womanpreference = new int[lenth][];
for (int i = 0; i < lenth; i++)
{
manpreference[i] = new int[lenth];
randomGenerator(manpreference[i]);
womanpreference[i] = new int[lenth];
randomGenerator(womanpreference[i]);
}
}
//Store the list values in random order most significant to least significant
private void randomGenerator(int[] vector)
{
for (int i = 0; i < vector.Length; i++)
vector[i] = i;
//Create the random permutation
for (int i = vector.Length - 1; i > 0; i--)
{
int j = rnd.Next(i + 1);//Random value generate
int temp = vector[i];//Swap the values v[i] and random value v[j]
vector[i] = vector[j];
vector[j] = temp;
}
}
//Argument parse to the showMatrix() method to print tables
private void showPreftable(string[] manlist, string[] womanlist)
{
Console.WriteLine("Woman Preference order :\n");
showMatrix(manpreference, manlist, womanlist);
Console.WriteLine("\nMan Preference order :\n");
showMatrix(womanpreference, womanlist, manlist);
}
//Display the matrix of preference order of men and women list
private void showMatrix(int[][] matrix, string[] memberlist, string[] referencelist)
{
if (matrix == null)
Console.WriteLine("Can't visible preference table");
for (int i = 0; i < matrix.Length; i++)
{
Console.Write(referencelist[i] + "\t-\t");
for (int j = 0; j < matrix[i].Length; j++)
{
Console.Write(memberlist[matrix[i][j]] + "\t\t");
}
Console.WriteLine();
}
}
//Return a stable married couples array where currentCouple[i] is the man married to woman i
private int[] stableCouple()
{
int[] currentCouple = new int[numofcouple];//Woman i is currently engaged to the man vector[i]
const int NOT_ENGAGED = -1;
for (int i = 0; i < currentCouple.Length; i++)
currentCouple[i] = NOT_ENGAGED;
//Queue of men that who are not currently engaged
LinkedList freemen = new LinkedList();
for (int i = 0; i < currentCouple.Length; i++)
{
freemen.Add(i);
}
//This is for the (nextPosition[i]) next woman to ehome i has not proposed
int[] nextPosition = new int[numofcouple];
//Breadth First Search through the bipartite graph
while (!freemen.isEmpty())
{
int man = freemen.Remove().iData;//Remove the first item from the queue
int woman = manpreference[man][nextPosition[man]];//Check that item bipartite connection
nextPosition[man]++;
//Check whether currently corrosponding woman is not engaged yet
if (currentCouple[woman] == NOT_ENGAGED)
{
currentCouple[woman] = man;
}
else
{
int otherman = currentCouple[woman];
if (preferenceOrder(woman, man, otherman))
{
currentCouple[woman] = man;
freemen.Add(otherman);
}
else
freemen.Add(man);
}
}
return currentCouple;
}
//Returns true if woman prefers man to otherman
private bool preferenceOrder(int woman, int man, int otherman)
{
for (int i = 0; i < numofcouple; i++)
{
int preference = womanpreference[woman][i];
if (preference == man)
return true;
if (preference == otherman)
return false;
}
Console.WriteLine("Invalid preference occur in woman list : " + woman);
return false;
}
//Display the matrix of marriedCouples
private void showMarriagecouples(int[] marriedcouple, string[] manlist, string[] womanlist)
{
Console.WriteLine("List of married couples :\n");
Console.WriteLine("Woman" + "\t\t" + "Man");
Console.WriteLine("----------------------");
for (int i = 0; i < marriedcouple.Length; i++)
{
Console.WriteLine(womanlist[i] + "\t+\t" + manlist[marriedcouple[i]]);
}
}
}
}
LinkedList.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace StableMarriedcouplewithBFS
{
//LinkedList Queue Implementation
class LinkedList
{
private Link first;//Link to the first node
private Link last;//Link to the last node
//Constructor for the LinkedList
public LinkedList()
{
first = null;
last = null;
}
//Check whether LinkedList is empty
public bool isEmpty()
{
return (first == null);
}
//Add an element to the queue to rear
public void Add(int id)
{
Link newLink = new Link(id);
if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}
//Remove the nodes from the front of the queue (FIFO)
public Link Remove()
{
Link temp = first;
if (first.next == null)
last = null;
first = first.next;
return temp;
}
}
}
Link.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace StableMarriedcouplewithBFS
{
class Link
{//Node class to the LinkedList
public int iData;//LinkedList store only integer value
public Link next;//Reference to the nest link of the LinkedList
//Constructor to the store value in LinkedList
public Link(int id)
{
iData = id;
}
}
}
Comments
Post a Comment