Stable marriage Problem. Let Man and Woman each be arrays of n processes. Each m
ID: 3802886 • Letter: S
Question
Stable marriage Problem. Let Man and Woman each be arrays of n processes. Each man ranks the women from 1 to n, and each woman ranks the men from 1 to n. A pairing is a one-to-one correspondence of men and women. A pairing is stable if, for two men m1 and m2 and their paired women w 1 and w2, both of the following conditions are satisfied: m1 ranks w1 higher than w2 or w2 ranks m2 higher than m1; and m2 ranks W2 higher than w1 or W1 ranks m1 higher than m2. Expressed differently, a pairing is unstable if a man and woman would both prefer each other to their current pair. A solution to the stable marriage problem is a set of n pairings, all of which are stable. Write an Actors-based program using Java with Akka to simulate a solution to the stable marriage problem. The processes should communicate using asynchronous message passing. The men should propose and the women should listen. A woman has to accept the first proposal she gets because a better one might not come along; however, she can dump the first man if she later gets a better proposal.Explanation / Answer
/**
*
* Java Program to Implement Stable Marriage Algorithm *
*
*/
/**
* Class GaleShapley *
*/
public class StableMarriage {
private int N, engagedCount;
private String[][] menPref;
private String[][] womenPref;
private String[] men;
private String[] women;
private String[] womenPartner;
private boolean[] menEngaged;
/**
* Constructor *
*/
public StableMarriage(String[] m, String[] w, String[][] mp, String[][] wp) {
N = mp.length;
engagedCount = 0;
men = m;
women = w;
menPref = mp;
womenPref = wp;
menEngaged = new boolean[N];
womenPartner = new String[N];
calcMatches();
}
/**
* function to calculate all matches *
*/
private void calcMatches() {
while (engagedCount < N) {
int free;
for (free = 0; free < N; free++) {
if (!menEngaged[free]) {
break;
}
}
for (int i = 0; i < N && !menEngaged[free]; i++) {
int index = womenIndexOf(menPref[free][i]);
if (womenPartner[index] == null) {
womenPartner[index] = men[free];
menEngaged[free] = true;
engagedCount++;
} else {
String currentPartner = womenPartner[index];
if (morePreference(currentPartner, men[free], index)) {
womenPartner[index] = men[free];
menEngaged[free] = true;
menEngaged[menIndexOf(currentPartner)] = false;
}
}
}
}
printCouples();
}
/**
* function to check if women prefers new partner over old assigned partner *
*/
private boolean morePreference(String curPartner, String newPartner, int index) {
for (int i = 0; i < N; i++) {
if (womenPref[index][i].equals(newPartner)) {
return true;
}
if (womenPref[index][i].equals(curPartner)) {
return false;
}
}
return false;
}
/**
* get men index *
*/
private int menIndexOf(String str) {
for (int i = 0; i < N; i++) {
if (men[i].equals(str)) {
return i;
}
}
return -1;
}
/**
* get women index *
*/
private int womenIndexOf(String str) {
for (int i = 0; i < N; i++) {
if (women[i].equals(str)) {
return i;
}
}
return -1;
}
/**
* print couples *
*/
public void printCouples() {
System.out.println("Couples are : ");
for (int i = 0; i < N; i++) {
System.out.println(womenPartner[i] + " " + women[i]);
}
}
/**
* main function *
*/
public static void main(String[] args) {
System.out.println("Stable Marriage Solution ");
/**
* list of men *
*/
String[] m = {"M1", "M2", "M3", "M4", "M5"};
/**
* list of women *
*/
String[] w = {"W1", "W2", "W3", "W4", "W5"};
/**
* men preference *
*/
String[][] mp = {{"W5", "W2", "W3", "W4", "W1"},
{"W2", "W5", "W1", "W3", "W4"},
{"W4", "W3", "W2", "W1", "W5"},
{"W1", "W2", "W3", "W4", "W5"},
{"W5", "W2", "W3", "W4", "W1"}};
/**
* women preference *
*/
String[][] wp = {{"M5", "M3", "M4", "M1", "M2"},
{"M1", "M2", "M3", "M5", "M4"},
{"M4", "M5", "M3", "M2", "M1"},
{"M5", "M2", "M1", "M4", "M3"},
{"M2", "M1", "M4", "M3", "M5"}};
StableMarriage sm = new StableMarriage(m, w, mp, wp);
}
}
Output:
Stable Marriage Solution
Couples are :
M4 W1
M2 W2
M5 W3
M3 W4
M1 W5
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.