spanish - types of algorithms




¿Repartir a la gente en habitaciones por apellido? (3)

A menudo enseño grandes clases de programación introductoria (400 - 600 estudiantes) y cuando llega el momento del examen, a menudo tenemos que dividir la clase en diferentes salones para asegurarnos de que todos tengan un asiento para el examen.

Para mantener las cosas logísticamente sencillas, generalmente separo la clase por apellido. Por ejemplo, podría enviar a los alumnos con los apellidos A - H a una sala, los apellidos I - L a una segunda sala, M - S a una tercera sala y T - Z a una cuarta sala.

El desafío al hacer esto es que las salas a menudo tienen capacidades muy diferentes y puede ser difícil encontrar una manera de segmentar a la clase de una manera que haga que todos se ajusten. Por ejemplo, suponga que la distribución de los apellidos es (por simplicidad) lo siguiente:

  • El apellido comienza con A: 25
  • El apellido comienza con B: 150
  • El apellido comienza con C: 200
  • El apellido comienza con D: 50

Supongamos que tengo salas con capacidades de 350, 50 y 50. Un algoritmo codicioso para encontrar una asignación de sala podría ser clasificar las salas en orden descendente de capacidad, luego tratar de llenar las salas en ese orden. Esto, desafortunadamente, no siempre funciona. Por ejemplo, en este caso, la opción correcta es colocar el apellido A en una sala de tamaño 50, los apellidos B - C en la sala de tamaño 350 y el apellido D en otra sala de tamaño 50. El algoritmo codicioso ponga los apellidos A y B en la sala de 350 personas, luego no encuentre asientos para todos los demás.

Es fácil resolver este problema simplemente probando todas las posibles permutaciones de los ordenamientos de las habitaciones y luego ejecutando el algoritmo codicioso en cada orden. Esto puede encontrar una asignación que funcione o informar que no existe. Sin embargo, me pregunto si hay una forma más eficiente de hacerlo, dado que la cantidad de habitaciones puede estar entre 10 y 20 y no es posible verificar todas las permutaciones.

Para resumir, la declaración formal del problema es la siguiente:

Se le da un histograma de frecuencia de los apellidos de los estudiantes en una clase, junto con una lista de salas y sus capacidades. Su objetivo es dividir a los estudiantes con la primera letra de su apellido para que a cada sala se le asigne un bloque de letras contiguo y no exceda su capacidad.

¿Existe un algoritmo eficiente para esto, o al menos uno que sea eficiente para tamaños de habitación razonables?

EDITAR: Muchas personas han preguntado acerca de la condición contigua. Las reglas son

  • Cada habitación debe estar asignada a lo más un bloque de letras contiguas, y
  • Ninguna carta debe ser asignada a dos o más habitaciones.

Por ejemplo, no puede colocar A - E, H - N y P - Z en la misma habitación. Tampoco puede poner A - C en una habitación y B - D en otra.

¡Gracias!


¿Hay alguna razón para hacer la vida tan complicada? ¿Por qué no puede asignar números de registro a cada estudiante y luego usar el número para asignarlos de la forma que desee? No es necesario que escriba un código, los estudiantes están contentos, todos están contentos.


Aquí hay un enfoque que debería funcionar razonablemente bien, dados los supuestos comunes sobre la distribución de los apellidos por inicial. Llene las habitaciones desde la capacidad más pequeña a la más grande de la manera más compacta posible dentro de las restricciones, sin retroceso.

Parece razonable (al menos para mí) que la sala más grande aparezca en el último lugar, ya que es para "todos los demás" que no están en la lista.


Se puede resolver utilizando algún tipo de solución DP en el espacio [m, 2^n] , donde m es el número de letras (26 para el inglés) y n es el número de habitaciones. Con m == 26 y n == 20 tomará aproximadamente 100 MB de espacio y ~ 1 segundo de tiempo. A continuación, se encuentra la solución que acabo de implementar en C # (se compilará con éxito en C ++ y Java también, solo se necesitarán algunos cambios menores):

int[] GetAssignments(int[] studentsPerLetter, int[] rooms)
{
    int numberOfRooms = rooms.Length;
    int numberOfLetters = studentsPerLetter.Length;
    int roomSets = 1 << numberOfRooms; // 2 ^ (number of rooms)
    int[,] map = new int[numberOfLetters + 1, roomSets];

    for (int i = 0; i <= numberOfLetters; i++)
        for (int j = 0; j < roomSets; j++)
            map[i, j] = -2;

    map[0, 0] = -1; // starting condition

    for (int i = 0; i < numberOfLetters; i++)
        for (int j = 0; j < roomSets; j++)
            if (map[i, j] > -2)
            {
                for (int k = 0; k < numberOfRooms; k++)
                    if ((j & (1 << k)) == 0)
                    {
                        // this room is empty yet.
                        int roomCapacity = rooms[k];
                        int t = i;
                        for (; t < numberOfLetters && roomCapacity >= studentsPerLetter[t]; t++)
                            roomCapacity -= studentsPerLetter[t];

                        // marking next state as good, also specifying index of just occupied room
                        // - it will help to construct solution backwards.
                        map[t, j | (1 << k)] = k;
                    }
            }

    // Constructing solution.
    int[] res = new int[numberOfLetters];
    int lastIndex = numberOfLetters - 1;
    for (int j = 0; j < roomSets; j++)
    {
        int roomMask = j;
        while (map[lastIndex + 1, roomMask] > -1)
        {
            int lastRoom = map[lastIndex + 1, roomMask];
            int roomCapacity = rooms[lastRoom];
            for (; lastIndex >= 0 && roomCapacity >= studentsPerLetter[lastIndex]; lastIndex--)
            {
                res[lastIndex] = lastRoom;
                roomCapacity -= studentsPerLetter[lastIndex];
            }

            roomMask ^= 1 << lastRoom; // Remove last room from set.

            j = roomSets; // Over outer loop.
        }
    }

    return lastIndex > -1 ? null : res;
}

Ejemplo de pregunta OP:

int[] studentsPerLetter = { 25, 150, 200, 50 };
int[] rooms = { 350, 50, 50 };
int[] ans = GetAssignments(studentsPerLetter, rooms);

La respuesta será:

2
0
0
1

Lo que indica el índice de espacio para cada una de las letras del apellido del estudiante. Si la asignación no es posible, mi solución volverá null .

[Editar]

Después de miles de pruebas generadas automáticamente, mi amigo encontró un error en el código que construye la solución al revés. No influye en algo principal, por lo que corregir este error será un ejercicio para el lector.

El caso de prueba que revela el error es students = [13,75,21,49,3,12,27,7] y rooms = [6,82,89,6,56] . Mi solución no responde, pero en realidad hay una respuesta. Tenga en cuenta que la primera parte de la solución funciona correctamente, pero la parte de construcción de la respuesta falla.





algorithm