Preference Based Grouping Algorithm

Question

I want to figure out a way to sort people by class by preference.

For example, let's say that 100 students, each of whom will be assigned one of the five classes:

• Science - 40 places.
• Mathematics - 15 places.
• History - 15 places.
• Computers - 20 places.
• Letter - 10 places.

Each student has three preferred classes, which are sorted by preference. What is the best way to approach student separation so that as many people as possible choose their first and second choice classes, while making sure that there are not too many students in the class for the room.

I thought of approaching it in the following way:

• Group all students in first class
• See which classes have too many students and who have too few
• Check if students from the above classes of the second class who are under subscription participate
• Move these students accordingly.
• Repeat 2-4 with the 3rd grade of choice

While I feel that this is a reasonable implementation, I wonder if there are other algorithms that better solve this problem. I tried searching all over, but I can’t find anything that could solve this problem.

Answer 1

From your description, this is very similar to one of the options Stable marriage problem

Check out the Wiki link and you will see a description of the Gale-Shapley algorithm, which is a good solution.