Python Algorithms – Stable Matching Problem

 

Some time ago I started to interest myself in algorithms. Thus, I bought 2 books about them and I started to read 🙂

Python

The first problem in the first book was explaining the Stable Matching Problem. The essence of the problem is that if you have n males and females, all of which wanting to get married, you should come up with an algorithm to propose who should marry who. Or if we use the terms from wikipedia:

The stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is stable whenever it is not the case that both: some given element A of the first matched set prefers some given element B of the second matched set over the element to which A is already matched, and B also prefers A over the element to which B is already matched.

Thus, I have checked the solution of the problem with the G-S algorithm and I saw that it takes less than 20 lines for the description. Thus, I tought that it can probably be something that I can mimic in Python. And so I started doing this about 3 hours ago. This is what I did:

  1. Creating two lists – one for males and one for females.
  2. In the lists, adding a dictionary with some properties of the users.
  3. Developing of useful functions, that were used in my code.
  4. Lots of tests until I come up with something reasonable.

The functions I have thought that will be useful for me were the following:

  • break_engagement(person) – breaking the engagement of someone;
  • is_engaged_to(person) – checking what is the name of the person someone is engaged to;
  • is_engaged(person) – just a boolean, returning whether the person is engaged;
  • who_do_you_love_more(person, candidate1, candidate2) – checking for the position of candidate1 and candidate2 in the list of the person;
  • engage(dramaKing, dramaQueen) – setting the King and the Queen to engagement;
  • get_name_from_ranking(dramaKing, rank) – this takes the name of the n-th unit in the list of the dramaKing;
  • main() – not going to explain it;
  • happyend() – printing the engaged couples, after the main is ran.

So, after I started with something like this:

So, what can we conclude from the given data inititally? We see that the less wanted male is the one with “F” and the less wanted female is “60”. Concerning the most wanted male, we do not know – we see that “A”, “C” or “B” are the ones on the top. The females are “10” and “20”. Thus, what is the result? A possible one is this:

whodoyoulove

 

As you see, we have a stable matching. We even had 3 breakings during it, but that is for the good of the stability – 20 has initially settled an engagement with “B”, but as far as “C” started to loop she decided to go for him. And something similar for F and D. One can write a “Santa-Barbara” generator with Python, if interested.

Pretty much that is all.

Here comes the code:

Enjoy it!

Tagged with: , , ,