The Problem: Programming Problem Stable Marriage Using Backtracking You have n m

Question

The Problem:

Programming Problem Stable Marriage Using Backtracking

You have n men and n woman, and their preference rankings of each other, and you need to match them up so that the total matching is “stable.”

The preference rankings:
You are given 2 n X n arrays, mp (men’s preference) which gives the men’s ranking of the

women, and wp (women’s preference) which gives the women’s ranking of the men.
So mp[i][j] gives man i's ranking of woman j and likewise for the women’s ranking of the men in

wp.

For example in the following tables we have n=3 and the women and men are “named” 0, 1 or 2 and the raking are in the range 0 = highest, 1 second highest and 2 lowest.

int mp[3][3]={0,2,1,

0,2,1,

1,2,0};

int wp[3][3]={2,1,0,

0,1,2,

2,0,1};
So man 1 assigns woman 2 the rank of 1 (i.e. second highest) and prefers woman 0 the best.

What is a stable matching?

A matching is stable if there are no “instabilities.” Say the match assigns m1 to w1 and m2 to w2. An instability is the situation where there is a mutual greater preference for the other person’s partner than for one’s own. For example m1 would prefer w2 to w1 and likewise w2 prefers m1 to m2.

How to do it:

Use the same approach that we used for the one dimensional eight queens problem. In the array q, q[i] is the woman assigned to man i.

The main program stays the same, besides the limits on the loops. All that needs to change is the ok function. Is could look something like this:

bool ok(int q[], int col) {

col indicates the new man and q[col] the new woman proposed to be added to the match.

We need to do 2 tests:

If the new woman has already been assigned to some man then return false

Check the new pair (new man, new woman) against each existing pair consisting of (current man, current woman) to see if the new pair would make the match unstable. So

if the current man prefers the new woman to his partner and

if the new woman prefers the current man to her partner

i. this is unstable, so return false
c. if the new man prefers the current woman to his partner and d. if the current woman prefers the new man to her partner

i. This is unstable, so return false
e. if there are no instabilities introduced with any of the existing (i.e. “current”)

}

couples, so we return true.

Input Data:

For this program use the arrays mp and wp above. The data will thus be “given” and not obtained by reading it in.

Output:

Print out all stable matchings, one per line. This is the same output that we did with the one dimensional eight queens program.

Example: Here are the preference tables MP and WP from before. MP WP 0 0 Will “2 0 1" be a solution? This is the following match: Man Woman What about "2 1 0”?

Explanation / Answer

men women

0 2

1 0

2 1

example of stability: WO is matched with M1, but she prefers M2, and likewise M2 prefers WO to his current partner W1.

Thus the following is not a correct solution.(it should be eliminated by OK function)

q

0 1 2

int mp[3][3]={0,2,1

0,2,1

1,2,0};

int wp[3][3]={2,1,0

0,1,2,

2,0,1}

so man 1 assigns W2 the rank of 1

bool OK(int q[],int c) {

/* c indicates the new man and q[c] is the woman proposed for man c*/

}

WP   

0 1 2

MP

0 1 2

would 102 be a solution?

0 1 0 1 0 < -----------------1   

1 -------------------->0 1 --------------------> 0 1 0

2 2 2 --------------------> 2 2< ---------------- 2

There are 3 cases:

case 1: MO prefers WO ; but its not a danger because WO prefers its own partner.

case 2: M1 prefers W0 to W2, so o instability, similarly M2 prefers W2 to WO.

case 3:MO prefers W2 to W1, but W2 prefers her wn partner to MO. So no instability.W1 prefers MO preference of M2, there would be no instability.

2 0 1

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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