# Can you marry them?

**Computer Science**Level 5

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
- \(rankMen\) is the rankings men provide for the women.
- For easier parsing, the data is available here

\[ 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} \]

\[ 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)\) to a disjunct *set of women* \((W)\) such that

- for every man \( m \in M \), there is a corresponding woman given by \( wife(m) \)
- for every woman \( w \in W \), there is a corresponding man given by \( husband(m) \)
- \(wife\) and \(husband\) are inverse functions. That is, \[ 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)\) such that

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