Stable Marriage is, skip to the end for a list of definitions.)
(For those who do not know what aGiven the following rankings of 9 men and 9 women, how many stable marriages between them exist?
r a n k M e n m , w = A B C D E F G H I a 7 5 4 9 2 2 1 5 6 b 3 4 8 7 6 7 6 6 1 c 8 8 3 4 4 8 2 9 4 d 9 3 9 2 9 6 3 1 7 e 6 1 7 5 8 5 8 2 5 f 4 2 5 8 7 3 5 8 8 g 2 6 6 3 5 4 4 4 3 h 1 7 1 1 1 1 9 3 9 i 5 9 2 6 3 9 7 7 2
r a n k W o m e n w , m = a b c d e f g h i A 3 9 3 8 6 2 9 6 8 B 1 4 1 7 9 4 3 3 2 C 5 8 8 5 2 5 8 2 6 D 2 1 9 3 5 1 2 1 4 E 8 7 5 2 1 6 7 8 9 F 7 6 4 6 4 8 5 4 1 G 6 3 2 4 7 3 4 5 3 H 9 2 6 9 3 9 6 9 7 I 4 5 7 1 8 7 1 7 5
A marriage is a relation between a set of men ( M ) to a disjunct set of women ( W ) such that
(If you find this confusing, the normal idea of a marriage is okay.)
Assume that every men has a ranking of preferences of the women and every women has a ranking of preferences of the men.
A marriage is considered stable iff there exists no pair of men and women ( m , w ) such that
r a n k m ( w ) < r a n k m ( w i f e ( m ) ) and r a n k w ( m ) < r a n k w ( h u s b a n d ( w ) )
(There are no two people of opposite sex who would both rather have each other than their current partners.)
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
You might consider recasting this with an original solution. It's a very cool problem and would be great to see it implemented in a more widely used language.
How can I improve my algorithm writing skill?Any suggestion?Any good website or book?
In short, how can I become a good programmer?
Thanks!
Log in to reply
Check this thread and let's continue this discussion there
Log in to reply
How did you started your journey?
As a typical Indian teenager, due to various exams, i can't focus on serious programming.Thus i can only give about 2-3 hrs in 3-4 days per week.But after i get into a college, i'll work hard.
Problem Loading...
Note Loading...
Set Loading...
An emerging field of research in computer science is Constraint Programming, on which I will do an wiki when I can. Constraint Programming lets you create models which you can feed into very well crafted constraint solvers instead of dictating the way to solve directly.
The solution is from Hakan's website
Over here, we model the men and the women with numbers from 1 to 9 instead of letters, which I used in the problem for clarity. The wife and husband functions are modelled with arrays indexed from 1 to 9.
The constraints are the same as we described in the problem with formal Kaboobly Doo. You might want to notice that we have described more constraints than needed. These are called redundant constraints in technical literature and are often useful to speed up the solving process.
Minizinc Code:
Run with
Outputs:
If you are interested in the powers constraint programming, I strongly recommend this or this course.