Quick access to my code if you prefer reading python code to my english.

I don’t want to reiterate the importance of recursion in the world. While in college, the math professor asked again and again to prove using recursion. And now I am in the programming world, I am still haunted by recursive programming. In a short sentence, I spent 2 hours today trying to write a recursive function in Python to calculate the perfect matching between two groups (bipartite).

I was taking Stanford’s MineMassiveDatasets from Coursera. There was a class where the lecturer was trying to match all the boys from a group to all the girls from another group :). There was a table given beforehand in where the possible relations between everyone are predefined. Say boyA can only date girlA or girlB, boyB can only date girlB..etc. The lecturer was so nice that he wants everyone to be in a relation in the end. Say lecturer arrange boyB to date girlB since he is so picky, and meanwhile boyA can compromise to choose girlA so he can do boyB a favor.. And in the end, all the vertices (people) will be matched in which a situation called perfect matching.

My first impression was to map the problem into a matrix, and probably can do some recursive programming to solve the problem. Honestly, I think my direction was right but I definitely underestimated the difficulty to get it done (I assume it will take me less than half an hour:( ).

After I put all relations into a tabular format, clearly the problem turned out to be find five 1s in the table where each 1 is the only 1 in the row and column it reside. i.e. every row(boy) or column(girl) has one and only one relationship (in real world, it should more interesting and complicated 🙂 ). Then Maybe we can start from the first row(boy). And then make two decisions, say if we let boy0 date girl0 or girl1 then the problem has been reduced to a perfect matching problem for the rest of the boys. Then once I start lift my fingers.. i realized it gonna take longer than I expected… not only because I was trying to use a tool that is new to me, pandas, numpy in iPython notebook, but also I have to do it in a recursive way.

You can have a brief idea of how it looks like in the end by visiting my github account.

The part that took me the most time is passing the existing relations into the next round of recursion.

The code is pretty simple.. but you can only assign a list to a new variable by value using slicing. And it seems like list slicing is also the most efficient way to do it.