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)
- 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