|
Stable marriage problemPuzzle: 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. Example: Given men m1 and m2 and women w1 and w2. Preference order of m1 is w1,w2 and that of m2 is also w1,w2. Preference order of w1 is m1,m2 and that of w2 is also m1,m2. Possible marriages among the above are:
The second system of marriages is less stable than the first one because there exists a combination where both m1 and w1 can find a better spouse as per their choice. While there is no such possibility in the first case, hence its more stable. 
Solution: An algorithm to do this as follows:
While there are bachelor men remaining, do the following:
Allow a man to propose to a woman.
If that woman has not accepted any proposal yet, she will accept the proposal.
If that woman has already accepted a proposal, she will break that if the new proposal is higher in her preference list.
If woman breaks her current alliance, the corresponding man will return to the pool of bachelors and have some wine.
When the pool of free men is over, everybody has been assigned a stable spouse.
And they live happily ever after.
Java code:
import java.util.*;
import java.util.Map.Entry;
public class StableMarriageProblem {
public static void main(String[] args)
{
// Preference order for 3 men
int men[][] = {
{0,1,2},
{0,1,2},
{0,1,2}
};
// Preference order for 3 women
int women[][] = {
{1,0,2},
{1,2,0},
{0,1,2}
};
// Add all available men to a HashSet, so its easy to lookup remaining bachelors
Set<Integer> availableMen = new HashSet <Integer> ();
for (int i=0; i<men.length; i++)
availableMen.add(i);
// Store alliance of a women in a HashMap.
// Null value means no alliance.
Map<Integer, Integer> availableWomen = new HashMap <Integer, Integer> ();
for (int i=0; i<women.length; i++)
availableWomen.put(i, null);
// Loop till there are bachelor men available
int size = availableMen.size();
while (size > 0)
{
int currentBachelor = availableMen.iterator().next();
System.out.println ("\nMan " + currentBachelor + " arrives:");
for (int w : men[currentBachelor]) // loop through preferences of this man
{
Integer fiance = availableWomen.get(w);
if (fiance == null) // this woman is not yet engaged
{
availableWomen.put(w, currentBachelor);
availableMen.remove(currentBachelor);
System.out.println ("Man " + currentBachelor + " engaged to woman " + w);
break;
}
else // this woman is currently engaged
{
int prefForFiance = -1;
int prefForCurrentBachelor = -1;
for (int k=0; k<women[w].length; k++)
{
if (women[w][k] == fiance) // find preference order for current fiance
prefForFiance = k;
if (women[w][k] == currentBachelor) // find preference order for current proposer
prefForCurrentBachelor = k;
}
if (prefForCurrentBachelor < prefForFiance) // nextBachelor has higher preference by this woman
{
availableWomen.put (w, currentBachelor); // accept current bachelor
availableMen.remove(currentBachelor);
availableMen.add(fiance); // return previous fiance to bachelors' pool
System.out.println ("Man " + fiance + " is dumped by woman " + w);
System.out.println ("Man " + currentBachelor + " engaged to woman " + w);
break;
}
}
}
size = availableMen.size();
}
// Print out the alliances
System.out.println();
Iterator<Entry<Integer, Integer>> itr = availableWomen.entrySet().iterator();
while (itr.hasNext())
{
Entry<Integer, Integer> entry = itr.next();
System.out.println ("Man " + entry.getValue() + " married to woman " + entry.getKey());
}
}
}
Sample Run:
Note that this problem does not consider the unhappiness of people who did not get the spouses of their choice. Maybe there were people who absolutely hated each other and would not sustain a marriage if married. If that were the case, then the above problem would need to have weights associated with each preference. Something like:
// Preference order for 3 men, along with weights for their preferences
int men[][][2] = {
{ {0,90} ,{1,50} ,{2,20} },
{ {0,80} ,{1,60} ,{2,40} },
{ {0,60} ,{1,50} ,{2,40} }
};
// Preference order for 3 women, along with weights for their preferences
int women[][][2] = {
{ {1,30} ,{0,20} ,{2,10} },
{ {1,90} ,{2,50} ,{0,10} },
{ {0,70} ,{1,50} ,{2,30} }
};
For such a case, following algorithm might work:
While there are bachelor men remaining, do the following:
Allow a man to propose to a woman.
If that woman has not accepted any proposal yet, she will accept the proposal.
If that woman has already accepted a proposal, she will break that if
|
Got a thought to share or found a
bug in the code?
We'd love to hear from you:
| Name: | |
| Email: | (Your email is not shared with anybody) |
| Comment: |
Facebook comments:
