Stable Marriage Problem


This is a very interesting problem where we need to find the most appropriate matching of set of males and set of females such that we can assign the pairs having the best scenario i.e there must not exist two pair {m1,w1} and {m2,w2} such that m1 and w2 would prefer each other more that their current partners.


So we’ll have the preference order of each and every person who they want to get married (obviously of opposite sex).

So its been proved that we can always make a stable matching.

( You can refer this link if you’re interested in proof )

Okay so lets discuss how the algorithm works :

So the main idea is to iterate over all the free men. That have not been matched till yet and then iterate over all the women according to their preference list. If the woman is free then just match this man and woman. Else if not then check the preference of this woman. If this man is preferred more over the current partner of this woman then the woman will dump the current partner and get matched with this man.


This way the algorithm continues till all the men and women get matched.

This is how the pseudo code looks like -

-> iterate over all the free man

{

-> iterate over this free man preference order .

-> check if this woman is free or not

YES? -> match this man and woman.

NO? -> check if this man is preferred more

than her current partner.

YES? -> Dump current partner and

Match these two.

NO? -> go for the next woman.

}


Code -

Output -

Time analysis - We can easily see that the given algorithm runs in O(n^2) time. As we’ve done a precomputation of checking is this man is preferred more than current partner in O(n^2) which gives the answer in O(1) everytime.

Hence time complexity is O(n^2).


This article is contributed by Satwik Tiwari

So that’s it for this article we will be coming up with our next article on further topics of Algorithms very soon till then keep learning, keep coding, keep reading and keep improving !!

Happy Coding

By Programmers Army 😊