[C++] [GSSoC'21] Stable Matching Problem - Gale Shapely Algorithm

[parthmshah1302]

• In this algorithm, we are given one set of N students and M set of hospitals. Every student ranks the hospitals as per their custom preference. Every hospital also ranks the students they want to intake as per their preference.

• The matching is considered stable when there is no student and hospital that would be matched otherwise than their current match.

• We are given the set of students and hospitals and have to return a stable match (which always exists)

Sample case: Input: A,B,C,D are the Students and p,q,r,s are the hospitals The preference of students are as follows: A:(p,q,r,s) B:{q,p,s,r} C:{q,s,r,p} D:{p,q,r,s}

The preference of hospitals are as follows: p:{A,C,B,D} q:{A,C,D,B} r:{D,B,A,C} s:{A,B,D,C}

Output: {(A,p),(B,s),(C,q),(D,r)} is a stable match (One can clearly see that there exists no student and hospital that would prefer each other more than their current match)

Note that this is not the only stable match.

I am a Participant of GSSoC'21, Can @rudrakshi99 @tarun26091999 @plazzy99 @nakul-19 @OjusWiZard @shreyanspoddar @raksha009 or any of the maintainers please assign me this issue in C++?

[parthmshah1302]

Solved in #1520 Please review!