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).
  1. 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
  2. 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.
Target: To find corresponding couple comparing each connection between men and women.

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

Popular posts from this blog

Solve the Maze by DFS (Depth First Search)

Image
In maze traversal, we must have to traverse deeper as soon as possible through the selected particular path until we reach the dead end. When we are on the way in that path, if it closed then we must have to back track to previous state to select another path. For this reasons, this traversal very similar to the DFS algorithm. Strategy for exploring Maze:  To convert given maze to a graph mark each intersection, corner and dead end (vertex) visited.  We mark each corridor (edge) as traversed.  We keep track of the path back to the entrance (start vertex) by means of a rope. (recursion stack) According to above all reasons, DFS (Depth First Search) algorithm very similar to a classic strategy for exploring a maze. Implementation in C# Graph.cs using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Maze_traversal {     class Graph     {        ...
Read more

Rabin Karp Algorithm

A military group is monitoring messages from terrorists which are transmitted as binary coded data streams. (a) The military is looking for an efficient way to search an identified pattern in the serial stream, in the data so far monitored, at a given time. In this setting, suppose the message T[1 ...n] is being transferred serially, in the order T[1],T[2],.... the military is interested in checking if the text seen so far contains a pattern P, where P has length m. Every time when the next letter of the text T is transmitted, it is necessary to check if the text seen so far contains P. (b) Now the terrorists are broadcasting reversed messages of the original message. So that although the same pattern P is used, the text T[1 ...n] is being transferred in reverse. That is, in the order T[n],T[n−1],... .Modify your algorithm so that it still detects the occurrence of P in the text T[i...n] immediately (i.e., in constant time) after the letter T[i] is seen. Implementation in C# ...
Read more

Text-to-Speech converter

Image
A speech recognition application will typically perform the following basic operations:  Initialize the speech recognizer.  Create a speech recognition grammar.  Load the grammar into the speech recognizer. Register for speech recognition event notification. Create a handler for the speech recognition event. Create a new project in Visual Studio 2010 via select the  File Menu  > New Project Browse to other languagues Select visual basic and windows application enter Name as TextToSpeechVB. when the project is created you have to add a reference to the System.Speech.dll under .NET Tab. Now design the form in following manner. 1. ComboBox control(cmbInstalled) - to list all available installed voices 2. Button Control(btnStart) - To starting the Text-to-Speech 3. Button Control(btnEnd) - To stop the Text-to-Speech 4. Track Bar control(btnRate) - to control the Text-to-Speech speed rate. 5. Trach Bar Control( btnVolume)- to ...
Read more