## Stable Marriage

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### Stable Marriage

In this work you will materialise a algorithm that solves the problem of Stable Marriage. In this problem we aim at "n" men and "n" women and our goal is the contracting of constant marriages between men and women. Obviously each man can be wedded only one woman and one woman one man similarly. Each individual, or man or woman, does not prefer to himself all the individuals of opposite sex but has a order of preference.
All men and the women can very easily shape "n" pairs between them. The problem is how stable are these marriages that are contracted. Be considered that between the wedded pairs, exist two pairs (a,g) and (a',g') where a and a' are men and g and g' women and that also a prefers more the g' from the g and the g' prefers more the a from the a'. It is very likely the a and the g' abandon their couples and become pair. Consequently, the question is finding "n" of pairs between men and women which constitutes viable marriages that is to say there should be no cases as the one that was reported above. The algorithm that it solves the problem of stable marriage is :

Initially all the men and women are free.There is a man "a" which is free and has not made proposal in any of the women.
Choose a such man "a".
Be it "g" the woman who has a higher ranking in the preferences of "a" and in which "a" has still not made proposal.
If the "g" is free then
"a" and "g" becomes pair.
Otherwise if the "g" is already pair with man "a'" then
If the g prefers more the "a'" from the "a" then
the "a" remains free.
Otherwise the g abandons the "a' " and becomes pair with the "a".
the "a" is henceforth free.
End If
End If
End While.

You are called materialise algorithm adopting suitable structures of data. Concretely, the structures that you will use will be supposed to ensure that each repetition of bronchus While requires time O(1), that is to say the crowd of action that is executed in a repetition of is constant independent size of problem "n". Also the structures that you will use will be supposed to occupy space o(n^2) maximum.
Finally, before the beginning of implementation of repetitive bronchus it can precede a phase of arhjkopoj'isis of structures where hrisjmopojsete. The cost in time of this phase should be very o(n^2).
Punkis

Posts: 10
Joined: Fri Apr 18, 2008 6:32 am

This kind of post usually meets the answer "What have you tried so far?", but in this case the translation is so poor that it's impossible to understand, and some details seem wrong (You can't possibly solve this problem using o(n^2) space).

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

He is just trying to match each man to a woman. It is simple double loop
Code: Select all
foreach man in MEN
if man is Not FREE
foreach woman in WOMEN

if woman and man BETTER MATCH
Divorce and Mary each other
End WOMEN
STAY MARRIED

Or something along those lines, I can't think about it right now.

ventsyv

Posts: 2810
Joined: Mon Sep 22, 2003 5:25 pm
Location: MD USA

What about the phase of arhjkopoj'isis of structures where hrisjmopojsete?

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

alvaro, why it can not be solved using o(n^2) space?
Punkis

Posts: 10
Joined: Fri Apr 18, 2008 6:32 am

so far..
Last edited by Punkis on Sat May 03, 2008 8:20 pm, edited 2 times in total.
Punkis

Posts: 10
Joined: Fri Apr 18, 2008 6:32 am

Punkis wrote:alvaro, why it can not be solved using o(n^2) space?

Because that would mean the space requirements is a function S(n) such that S(n)<C*n^2 for any constant C if n is sufficiently large. This is equivalent to saying that the limit of S(n)/n^2 is 0 as n goes to infinity. Since the description of the graph already takes space proportional to n^2, that limit won't be 0.

The problem probably says `O(n^2)' instead. Doesn't it?

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

so what about the code?
Punkis

Posts: 10
Joined: Fri Apr 18, 2008 6:32 am

Punkis wrote:so what about the code?

There is a `while (1)' in the code with no break statement in the body. How do you expect it will ever finish?

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

i love you alvaro ^o^
:]

schloob

Posts: 1853
Joined: Mon Feb 16, 2004 10:29 am
Location: Seattle

thank you alvaro..how do you find my code?
Punkis

Posts: 10
Joined: Fri Apr 18, 2008 6:32 am

I would find it better if you use the code tags ....

ventsyv

Posts: 2810
Joined: Mon Sep 22, 2003 5:25 pm
Location: MD USA

done!
Punkis

Posts: 10
Joined: Fri Apr 18, 2008 6:32 am

so..do you find it correct? is there anything i have to change?
Punkis

Posts: 10
Joined: Fri Apr 18, 2008 6:32 am

Looks fine to me. I can't say if it works correctly just by looking by it, but your solution does look reasonable. Does it work ??

ventsyv

Posts: 2810
Joined: Mon Sep 22, 2003 5:25 pm
Location: MD USA

Next