Stable Marriage

[Punkis]

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).

[Alvaro]

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).

[ventsyv]

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.

[Alvaro]

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

[Punkis]

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

[Punkis]

so far..

[Alvaro]

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?

[Punkis]

so what about the code?

[Alvaro]

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?

[schloob]

i love you alvaro ^o^

[Punkis]

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

[ventsyv]

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

[Punkis]

done!

[Punkis]

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

[ventsyv]

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 ??