algorithm - Algoritmo para la agrupación basada en preferencias

set grouping (1)

Estoy buscando una manera de clasificar personas en clases por preferencia.

Por ejemplo, supongamos que hay 100 alumnos a los que se les asignará una de cada cinco clases:

Ciencia - 40 asientos
Matemáticas - 15 asientos
Historia - 15 asientos
Computadoras - 20 asientos
Escritura - 10 asientos

Cada estudiante tiene tres clases preferidas que están ordenadas por preferencia. ¿Cuál es la mejor manera de abordar la división de los estudiantes para que tantas personas obtengan sus clases de primera y segunda opción como sea posible, mientras que al mismo tiempo se asegura de que ninguna clase tenga demasiados estudiantes para la sala?

He pensado en abordarlo por el siguiente método:

Agrupe a todos los estudiantes por su primera clase de elección
Vea qué clases tienen demasiados estudiantes y cuáles tienen muy pocos
Verifique si alguno de los estudiantes en las clases con sobreventa tiene clases de segunda opción que están sub-reservadas
Mueva a esos estudiantes en consecuencia
Repita del 2 al 4 con las clases de tercera opción

Si bien creo que esta es una implementación razonable, me pregunto si hay otros algoritmos que resuelvan este problema de una mejor manera. He intentado buscar por todas partes, pero no encuentro nada que pueda resolver este tipo de problema.

Según su descripción, esto se parece mucho a una de las variaciones del problema estable del matrimonio

Verifique el enlace Wiki y verá una descripción del algoritmo Gale-Shapley, que es una buena solución.