# Algo to match students to universities (only students choose & rank)

I'm trying to develop an algorithm in Ruby to allocate one university to each student of a list. As opposed to Gale-Shapley algorithm, universities do no choose nor rank students; only students make a 6-wish ordered list.

• There are 336 students
• There are 151 cities, each with an available number of places between 1 & 6

I think this boils down to computing a minimum sum of 'distances', a student's distance being the rank of the university he was attributed (in his ordered list). E.g: if a student is given his first choice, then his 'distance' is 0. If a student is given his last choice, then his 'distance' is 5.

I see 2 possibilities:

• brute-force to compute all the possibilities and find the one with the minimum sum of distances. But I think it would take too much time/very bad performance & complexity.
• determine criterion beforehand to allocate universities. E.g: we start by giving all non-disputed 1st choice cities to students (e.g if 4 students put 'Paris' as their first choice and Paris has more than 4 seats, we give these 4 students the Paris university). And then we can do the same all the way down to the 6th choices. But this will not give a university to all students, so we then need to find another criteria (or several other criterion) to allocate a university to each of the remaining students. There is another downside of this method: the allocation will depend on the criterion chosen and the algo will maybe not give the best output (minimum of sum of distances).

My questions are:

• do I need to use brute-force to find the optimal solution?
• if not, what are the 'best' criterion to allocate universities in this algorithm? ('best' meaning it will allow me to end up with the optimal solution, or if it can't, at least with a pretty good solution overall)

NB:

• I'm a beginner in Ruby & algo, I've read posts on different websites with a lot of theoretical knowledge required but that didn't help me, so if you could vulgarize that would be awesome :)
• I originally posted my question on StackOverflow
• For now, I'm not considering weighing choices non-linearly (e.g. a last choice 'costs' 10 instead of 5), as I think it will be easy to add once I know the right way to proceed
• Please do not post the same question on multiple sites. Thank you.
– D.W.
Jun 27, 2021 at 21:31
• I was advised to do so, but I won't next time. Thanks Jun 28, 2021 at 7:51
• I’m voting to close this question because the OP is interested mainly in solutions implementable in Ruby. Jun 28, 2021 at 9:35
• @eleove, I understand - from your perspective, you were just following what advice others were giving. My guess is they were just trying to help, but not everyone is familiar with this rule. Now you know about it. Also, I do want to highlight that, while I can see how it might have looked that way, I don't think they were actually recommending you cross-post -- they were trying to recommend a better site, which is consistent with the advice to delete your question there before posting here if you post it on the wrong site.
– D.W.
Jun 28, 2021 at 19:52

Construct a bipartite graph, where one side corresponds to students, and the other side corresponds to spots in cities: if a city has $$n$$ spots, there will be $$n$$ vertices corresponding to the city. If student $$x$$ is interested in city $$y$$, connect $$x$$ to all spots of $$y$$ with an edge whose weight corresponds to the "distance". Now compute a maximum weight perfect matching (or a maximum weight matching, if you want to allow students to be unmatched).