300x250 AD TOP

Powered by Blogger.

Blog Archive

Thursday, 11 December 2014

Tagged under:

what crazy stats


You can apply Bipartite Matching algorithm of Graph Theory. All you have to do is:
  1. Put all girls as vertices (a's) in Part A, and boys as vertices (b's) in Part B.
  2. Draw an edge between vertex a to vertex b if a likes b.
  3. It will be a bipartite graph (there are no edges within vertices of Part A, and same for Part B) unless your friends are not straight.
  4. Then find maximum matching for this bipartite graph. (refer this linkMaximum Bipartite Matching - GeeksforGeeks)
  5. You will get maximum matching as output and the matched edges will be the pairs who should be together.
  6. You can apply weighted bipartite matching algorithm if you know how much they love/like each other. In that case, assign weights according to their amount of love. and repeat step 4 and 5.

Thanks for asking this question. Finally I have found a real life problem which can be solved by what Prof Panda has been teaching us for 2-3 years.

P.S. I can provide you code for both weighted and unweighted maximum bipartite matching which I made for my project.