Can you marry them?

Computer Science Level 5

(For those who do not know what a Stable Marriage is, skip to the end for a list of definitions.)

Given the following rankings of 9 men and 9 women, how many stable marriages between them exist?

  • A lower numerical rank denotes stronger preference.
  • The set of men is expressed in upper case and the set of women is expressed in lower case.
  • Each row denote the rankings of an individual
  • r a n k M e n rankMen is the rankings men provide for the women.
  • For easier parsing, the data is available here

r a n k M e n m , w = a b c d e f g h i A 7 3 8 9 6 4 2 1 5 B 5 4 8 3 1 2 6 7 9 C 4 8 3 9 7 5 6 1 2 D 9 7 4 2 5 8 3 1 6 E 2 6 4 9 8 7 5 1 3 F 2 7 8 6 5 3 4 1 9 G 1 6 2 3 8 5 4 9 7 H 5 6 9 1 2 8 4 3 7 I 6 1 4 7 5 8 3 9 2 rankMen_{m,w} = \begin{matrix} & a & b & c & d & e & f & g & h & i \\ A & 7 & 3 & 8 & 9 & 6 & 4 & 2 & 1 & 5 \\ B & 5 & 4 & 8 & 3 & 1 & 2 & 6 & 7 & 9 \\ C & 4 & 8 & 3 & 9 & 7 & 5 & 6 & 1 & 2 \\ D & 9 & 7 & 4 & 2 & 5 & 8 & 3 & 1 & 6 \\ E & 2 & 6 & 4 & 9 & 8 & 7 & 5 & 1 & 3 \\ F & 2 & 7 & 8 & 6 & 5 & 3 & 4 & 1 & 9 \\ G & 1 & 6 & 2 & 3 & 8 & 5 & 4 & 9 & 7 \\ H & 5 & 6 & 9 & 1 & 2 & 8 & 4 & 3 & 7 \\ I & 6 & 1 & 4 & 7 & 5 & 8 & 3 & 9 & 2 \end{matrix}

r a n k W o m e n w , m = A B C D E F G H I a 3 1 5 2 8 7 6 9 4 b 9 4 8 1 7 6 3 2 5 c 3 1 8 9 5 4 2 6 7 d 8 7 5 3 2 6 4 9 1 e 6 9 2 5 1 4 7 3 8 f 2 4 5 1 6 8 3 9 7 g 9 3 8 2 7 5 4 6 1 h 6 3 2 1 8 4 5 9 7 i 8 2 6 4 9 1 3 7 5 rankWomen_{w,m} = \begin{matrix} & A & B & C & D & E & F & G & H & I \\ a & 3 & 1 & 5 & 2 & 8 & 7 & 6 & 9 & 4 \\ b & 9 & 4 & 8 & 1 & 7 & 6 & 3 & 2 & 5 \\ c & 3 & 1 & 8 & 9 & 5 & 4 & 2 & 6 & 7 \\ d & 8 & 7 & 5 & 3 & 2 & 6 & 4 & 9 & 1 \\ e & 6 & 9 & 2 & 5 & 1 & 4 & 7 & 3 & 8 \\ f & 2 & 4 & 5 & 1 & 6 & 8 & 3 & 9 & 7 \\ g & 9 & 3 & 8 & 2 & 7 & 5 & 4 & 6 & 1 \\ h & 6 & 3 & 2 & 1 & 8 & 4 & 5 & 9 & 7 \\ i & 8 & 2 & 6 & 4 & 9 & 1 & 3 & 7 & 5 \end{matrix}

A marriage is a relation between a set of men ( M ) (M) to a disjunct set of women ( W ) (W) such that

  1. for every man m ∈ M m \in M , there is a corresponding woman given by w i f e ( m ) wife(m)
  2. for every woman w ∈ W w \in W , there is a corresponding man given by h u s b a n d ( m ) husband(m)
  3. w i f e wife and h u s b a n d husband are inverse functions. That is, w i f e ( h u s b a n d ( w ) ) = w ∀ w ∈ W h u s b a n d ( w i f e ( m ) ) = m ∀ m ∈ M wife(husband(w)) = w \quad \forall w \in W \\ husband(wife(m)) = m \quad \forall m \in M

(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 ) (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 ) ) rank_{m}(w) < rank_{m}(wife(m)) \quad \text{and} \\ rank_{w}(m) < rank_{w}(husband(w))

(There are no two people of opposite sex who would both rather have each other than their current partners.)


The answer is 6.

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

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.

1 solution

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: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
include "globals.mzn";

int: num_women = 9; 

array[1..num_women, 1..num_men] of var 1..num_men: rankWomen;
array[1..num_men, 1..num_women] of var 1..num_women: rankMen;

array[1..num_men] of var 1..num_women: wife;
array[1..num_women] of var 1..num_men: husband;

solve satisfy;

constraint
        forall(m in 1..num_men) ( 
            husband[wife[m]] = m 
        )  
        /\        
        forall(w in 1..num_women) ( 
           wife[husband[w]] = w 
        )  
        /\
        forall(m in 1..num_men, o in 1..num_women) (
           rankMen[m,o] < rankMen[m, wife[m]] ->
           rankWomen[o,husband[o]] < rankWomen[o,m]
        )
        /\
        forall(w in 1..num_women, o in 1..num_men) (
           rankWomen[w,o] < rankWomen[w,husband[w]] ->
           rankMen[o,wife[o]] < rankMen[o,w]
        )
;

output [
       "wife   : ", show(wife), "\n",
       "husband: ", show(husband), "\n",
]
;

rankMen = 
[|7, 3, 8, 9, 6, 4, 2, 1, 5,
 |5, 4, 8, 3, 1, 2, 6, 7, 9,
 |4, 8, 3, 9, 7, 5, 6, 1, 2,
 |9, 7, 4, 2, 5, 8, 3, 1, 6,
 |2, 6, 4, 9, 8, 7, 5, 1, 3,
 |2, 7, 8, 6, 5, 3, 4, 1, 9,
 |1, 6, 2, 3, 8, 5, 4, 9, 7,
 |5, 6, 9, 1, 2, 8, 4, 3, 7,
 |6, 1, 4, 7, 5, 8, 3, 9, 2,
 |];

rankWomen =
[|3, 1, 5, 2, 8, 7, 6, 9, 4,
 |9, 4, 8, 1, 7, 6, 3, 2, 5,
 |3, 1, 8, 9, 5, 4, 2, 6, 7,
 |8, 7, 5, 3, 2, 6, 4, 9, 1,
 |6, 9, 2, 5, 1, 4, 7, 3, 8,
 |2, 4, 5, 1, 6, 8, 3, 9, 7,
 |9, 3, 8, 2, 7, 5, 4, 6, 1,
 |6, 3, 2, 1, 8, 4, 5, 9, 7,
 |8, 2, 6, 4, 9, 1, 3, 7, 5
 |];

Run with 

1
 
./mzn-g12fd --all-solutions /tmp/stable_marriage.mzn

Outputs: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
 
wife   : [6, 4, 9, 8, 3, 7, 1, 5, 2]
husband: [7, 9, 5, 2, 8, 1, 6, 4, 3]
----------
wife   : [6, 5, 9, 8, 3, 7, 1, 4, 2]
husband: [7, 9, 5, 8, 2, 1, 6, 4, 3]
----------
wife   : [6, 4, 1, 8, 5, 7, 3, 2, 9]
husband: [3, 8, 7, 2, 5, 1, 6, 4, 9]
----------
wife   : [6, 1, 4, 8, 5, 7, 3, 2, 9]
husband: [2, 8, 7, 3, 5, 1, 6, 4, 9]
----------
wife   : [6, 1, 4, 8, 5, 9, 3, 2, 7]
husband: [2, 8, 7, 3, 5, 1, 9, 4, 6]
----------
wife   : [7, 5, 9, 8, 3, 6, 1, 4, 2]
husband: [7, 9, 5, 8, 2, 6, 1, 4, 3]
----------
==========

If you are interested in the powers constraint programming, I strongly recommend this or this course.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

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.

Hey @Agnishom Chattopadhyay

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!

Harsh Shrivastava - 5 years, 2 months ago

Log in to reply

Check this thread and let's continue this discussion there

Agnishom Chattopadhyay - 5 years, 2 months ago

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.

Harsh Shrivastava - 5 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...