This pseudocode of the GALE–SHAPLEY (preference lists for men and women): Initia

ID: 3782255 • Letter: T

Question

This pseudocode of the GALE–SHAPLEY (preference lists for men and women):

Initially all m M and w W are free
While there is a man m who is free and hasn’t proposed to every woman w
Choose such a man m
Let w be the highest-ranked woman in m’s preference list
to which m has not yet proposed
   If w is free then
   (m, w) become engaged
   Else w is currently engaged to m'
   If w prefers m' to m then
     m remains free
   Else w prefers m to m'
     (m, w) become engaged
     m' becomes free

Endif
Endif
Endwhile
Return the set S of engaged pairs

Reflects to the java code:

import java.util.*;
/**
* An implementation of the stable marriage algorithm from
* Chapter 1-2 in "Algorithm Design" by Kleinberg and Tardos.
*
*/
public class StableMarriage
{
// Number of men (=number of women)
private int n ;
// Preference tables (size nxn)
private int[][] manPref;
private int[][] womanPref;
private static final boolean DEBUGGING = false;
private Random rand = new Random();
/**
* Creates and solves a random stable marriage problem of
* size n, where n is given on the command line.
*/
public static void main(String[] args) {
if (args.length != 1) {
System.out.println("Usage: java StableMarriage n");
return;
}
int n = Integer.parseInt(args[0]);
StableMarriage sm = new StableMarriage(n);
if (n <= 10)
sm.printPrefTables();
int[] marriage = sm.stable();
if (n <= 10)
sm.printMarriage(marriage);
}
/**
* Creates a marriage problem of size n with random
preferences.
*/
public StableMarriage(int n) {
this.n = n;
manPref = new int[n][];
womanPref = new int[n][];
for (int i = 0; i < n; i++) {
manPref[i] = new int[n];
createRandomPrefs(manPref[i]);
womanPref[i] = new int[n];
createRandomPrefs(womanPref[i]);
}
}
/**
* Puts the numbers 0 .. v.length - 1 in the vector v
* in random order.
*/
private void createRandomPrefs(int[] v) {
// Create a vector with the values 0, 1, 2, ...
for (int i = 0; i < v.length; i++)
v[i] = i;
// Create a random permutation of this vector.
for (int i = v.length - 1; i > 0; i--) {
// swap v[i] with a random element v[j], j <= i.
int j = rand.nextInt(i+1);
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
}
/**
* Returns a stable marriage in the form an int array v,
* where v[i] is the man married to woman i.
*/
public int[] stable() {
// Indicates that woman i is currently engaged to
// the man v[i].
int[] current = new int[n];
final int NOT_ENGAGED = -1;
for (int i = 0; i < current.length; i++)
current[i] = NOT_ENGAGED;
// List of men that are not currently engaged.
LinkedList freeMen = new LinkedList();
for (int i = 0; i < current.length; i++)
freeMen.add(i);
// next[i] is the next woman to whom i has not yet proposed.
int[] next = new int[n];
//computeRanking();
while (!freeMen.isEmpty()) {
int m = freeMen.remove();
int w = manPref[m][next[m]];
next[m]++;
printDebug("m=" + m + " w=" + w);
if (current[w] == NOT_ENGAGED) {
current[w] = m;
} else {
int m1 = current[w];
if (prefers(w, m, m1)) {
current[w] = m;
freeMen.add(m1);
} else {
freeMen.add(m);
}
}
}
return current;
}
/**
* Returns true iff w prefers x to y.
*/
private boolean prefers(int w, int x, int y) {
for (int i = 0; i < n; i++) {
int pref = womanPref[w][i];
if (pref == x)
return true;
if (pref == y)
return false;
}
// This should never happen.
System.out.println("Error in womanPref list " + w);
return false;
}
public void printPrefTables() {
System.out.println("manPref:");
printMatrix(manPref);
System.out.println("womanPref:");
printMatrix(womanPref);
}
private void printMarriage(int[] m) {
System.out.println("Married couples (woman + man): ");
for (int i = 0; i < m.length; i++)
System.out.println(i + " + " + m[i]);
}
private void printDebug(String s) {
if (DEBUGGING) {
System.out.println(s);
}
}
/**
* Prints the matrix v.
*/
private void printMatrix(int[][] v) {
if (v == null) {
System.out.println("");
return;
}
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[i].length; j++)
System.out.print(v[i][j] + " ");
System.out.println();
}
}
}

Question: Modify the Java code above to match the following pseudocode:

Initially all m M and w W are free
While there is a man m who is free and hasn’t proposed to every woman w for which (m, w) F
Choose such a man m
Let w be the highest-ranked woman in m’s preference list
to which m has not yet proposed
   If w is free then
   (m, w) become engaged
   Else w is currently engaged to m'
   If w prefers m' to m then
     m remains free
   Else w prefers m to m'
     (m, w) become engaged
     m' becomes free
Endif
   Endif
Endwhile
Return the set S of engaged pairs

So basically, we don’t want m to propose to a woman w for which the pair (m, w) is forbidden and we want that to be reflected onto the Java code above.

Thus, let’s consider a variation of the G-S algorithm in which we make only one change: we modify the While loop to say,

While there is a man m who is free and hasn’t proposed to every woman w for which (m, w) F.

Explanation / Answer

Modification Logic -

1. Randomly create a list of forbidden couple

2. Check if the list contains the pair (of a male and a female)

3. If no, continue as before

4. If yes, skip w and pick another next highest preference w from the preference list

Modified StableCouple.java

/**
* Puts the numbers 0 .. v.length - 1 in the vector v
* in random order.
*/
private void createRandomPrefs(int[] v) {
// Create a vector with the values 0, 1, 2, ...
for (int i = 0; i < v.length; i++)
v[i] = i;
// Create a random permutation of this vector.
for (int i = v.length - 1; i > 0; i--) {
// swap v[i] with a random element v[j], j <= i.
int j = rand.nextInt(i+1);
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
}
/**
* Creates N*2 Random Forbidden Couples.
*/
private void createRandomForbiddenPairs() {
   int i=0;
   while(i<n*2){
       int randM = rand.nextInt(n);
       int randF = rand.nextInt(n);
       boolean newAdd = forbiddenPairs.add(new Pair(randM,randF));
       //if add unsuccessful i.e. Couple already present, then generate another random couple
       if(!newAdd)
           continue;
       i++;
   }
}
/**
* Returns a stable marriage in the form an int array v,
* where v[i] is the man married to woman i.
*/
public int[] stable() {
// Indicates that woman i is currently engaged to
// the man v[i].
int[] current = new int[n];
final int NOT_ENGAGED = -1;
for (int i = 0; i < current.length; i++)
current[i] = NOT_ENGAGED;
// List of men that are not currently engaged.
LinkedList freeMen = new LinkedList();
for (int i = 0; i < current.length; i++)
freeMen.add(i);
// next[i] is the next woman to whom i has not yet proposed.
int[] next = new int[n];
//computeRanking();
while (!freeMen.isEmpty()) {
int m = (int) freeMen.remove();
int w = manPref[m][next[m]];
next[m]++;
printDebug("m=" + m + " w=" + w);
Pair p = new Pair(m,w);
//If Forbidden Couple, then skip
if(!forbiddenPairs.contains(p)){
   if (current[w] == NOT_ENGAGED) {
       current[w] = m;
       } else {
       int m1 = current[w];
       if (prefers(w, m, m1)) {
       current[w] = m;
       freeMen.add(m1);
       } else {
       freeMen.add(m);
       }
       }
} else{
   printDebug("Forbidden Pair");
   //Re-add
   freeMen.add(m);
}
}
return current;
}
/**
* Returns true iff w prefers x to y.
*/
private boolean prefers(int w, int x, int y) {
for (int i = 0; i < n; i++) {
int pref = womanPref[w][i];
if (pref == x)
return true;
if (pref == y)
return false;
}
// This should never happen.
System.out.println("Error in womanPref list " + w);
return false;
}
public void printPrefTables() {
System.out.println("manPref:");
printMatrix(manPref);
System.out.println("womanPref:");
printMatrix(womanPref);

//Printing List of Forbidden Couples
System.out.println("Forbiden Couples");
Iterator<Pair> it = forbiddenPairs.iterator();
while(it.hasNext()){
   Pair p = (Pair) it.next();
   System.out.println(p.getM()+" + "+p.getF());
}

}
private void printMarriage(int[] m) {
System.out.println("Married couples (woman + man): ");
for (int i = 0; i < m.length; i++)
System.out.println(i + " + " + m[i]);
}
private void printDebug(String s) {
if (DEBUGGING) {
System.out.println(s);
}
}
/**
* Prints the matrix v.
*/
private void printMatrix(int[][] v) {
if (v == null) {
System.out.println("");
return;
}
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[i].length; j++)
System.out.print(v[i][j] + " ");
System.out.println();
}
}

/**
* Inner Pair Class to store a Couple
* @author Anonymous
*
*/
class Pair{
   int m;
   int f;

   Pair(int m, int f){
       this.m = m;
       this.f = f;
   }

   public int getM() {
       return m;
   }

   public int getF() {
       return f;
   }

   /**
   * Overriding Equals
   */
   @Override
   public boolean equals(Object obj) {
       if(obj instanceof Pair){
           Pair o = (Pair) obj;
           if(this.getM()==o.getM() && this.getF()==o.getF())
               return true;
           return false;
       }
       return false;
   }

   /**
   * Overriding hashCode
   */
   @Override
   public int hashCode() {
       return (m<<4)|f;
   }
}
}

Navigate

This proton has been “fired” from the left towards the right, in the uniform ele

This pseudocode segment is intended to describe computing thecost per day and th

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

This pseudocode of the GALE–SHAPLEY (preference lists for men and women): Initia

Question

Explanation / Answer

Related Questions

Navigate