Permutaciones en Filas; Problema de Optimización de Jardín

Question

Imagina un pequeño jardín, dividido en 8 partes iguales, cada una de un pie cuadrado. El jardín mide 4 pies x 2 pies, por lo que los "contenedores" están en dos filas. Vamos a numerarlos así:

0 1 2 3
4 5 6 7

Ahora, cada una de estas plantas tiene otras plantas que les gustan, que es bueno que estén cerca. Puedo calificar un arreglo en particular por cuántas de estas buenas relaciones termino teniendo. He hecho esto en un script de python, descrito aquí.

Sin repetir todos esos detalles aquí, mi problema es que hay demasiadas permutaciones. Si simplemente lo paso por el útil generador de permutaciones de python, hay 8! casos. (Estoy planteando este problema aquí como 8 espacios, pero mi jardín real tiene 16 contenedores. El problema es demasiado grande para resolverlo con 16! arreglos posibles.)

Mi pregunta matemática es, ¿cómo puedo iterar a través de una lista de permutaciones únicas que también consideren cómo están arregladas estas dos filas? Si todas estuvieran en una fila, la respuesta sería fácil, 8!. Con 2 filas, hay rotaciones y espejos que son realmente la misma respuesta.

0 1 2 3 es lo mismo cuando se refleja 3 2 1 0
4 5 6 7                           7 6 5 4

0 1 2 3 es lo mismo cuando se refleja 4 5 6 7
4 5 6 7                           0 1 2 3

0 1 2 3 es lo mismo cuando se rota  7 6 5 4
4 5 6 7                           3 2 1 0

Me gustaría calificar todos los arreglos posibles, pero saltar aquellos que son espejos o rotaciones de cosas que ya he considerado. Mis habituales intentos chapuceros de iterar a través de tales cosas incluyen una tabla de búsqueda, donde simplemente miraría a través de una lista de cosas completadas. En este caso, esa búsqueda a través potencialmente de 8! (16! en mi problema real) tomaría mucho más tiempo que simplemente calificar cada permutación.

¿Cómo puedo iterar a través de esto y potencialmente reducir mi conjunto de problemas de 16! (~20 trillones) a quizás 5 trillones? O, si no se puede responder directamente, ¿cómo llamarías a este tipo de problema? No estoy seguro de qué buscar y leer al respecto. ¡Si supiera lo suficiente como para saber qué etiquetar este problema, estaría más avanzado!

Answer 1

Puedes resolver este problema a través de programación lineal entera, como sigue. Deja que la variable binaria $x_{i,j}$ indique si el ítem $i$ está ubicado en el slot $j$. Maximizar el número de pares buenos es equivalente a minimizar el número de pares malos. Para cada par $(j_1,j_2)$ (con $j_1) de slots vecinos, deja que la variable binaria $y_{j_1,j_2}$ indique si el par de ítems asignados a esos slots es malo. El problema consiste en minimizar $\sum_{j_1,j_2} y_{j_1,j_2}$ sujeto a: \begin{align} \sum_j x_{i,j} &= 1 &&\text{para todo $i$}\\ \sum_i x_{i,j} &= 1 &&\text{para todo $j$}\\ x_{i_1,j_1} + x_{i_2,j_2} - 1 &\le y_{j_1,j_2} &&\text{para todos los pares de ítems malos $(i_1,i_2)$ (con $i_1 \neq i_2$) y pares de slots $(j_1,j_2)$} \end{align} La primera restricción coloca cada ítem en exactamente un slot. La segunda restricción coloca exactamente un ítem en cada slot. La tercera restricción impone la implicación $(x_{i_1,j_1} = 1 \land x_{i_2,j_2} = 1) \implies y_{j_1,j_2} = 1$, por lo que colocar un par de ítems malo en slots vecinos contribuye con una penalización de $1$ al objetivo.

Usar un solver de programación lineal entera encontrará una solución óptima sin enumerar explícitamente todas las soluciones factibles.

Answer 2

Puedes hacer esto usando canonización.

Siempre que el jardín sea rectangular, exactamente una de las permutaciones equivalentes tiene el $0$ en el cuarto superior izquierdo (para $2\times4$, esos son los primeros dos lugares), por lo que puedes verificar rápidamente si ese es el caso y solo procesar dichas permutaciones.

Si el jardín es cuadrado, las cosas son solo ligeramente más complicadas. Ahora hay dos permutaciones equivalentes donde el $0$ está en el cuarto superior izquierdo. Si el $0$ está fuera de la diagonal, toma aquella en la que esté por encima de la diagonal; si está en la diagonal, toma la que tenga los elementos fuera de la diagonal en el cuarto superior izquierdo en orden ascendente.

O siempre puedes tomar la permutación léxicamente más pequeña. Esa es aquella donde el valor más pequeño en las cuatro esquinas está en la esquina superior izquierda, y en caso de un cuadrado, adicionalmente el valor a la derecha de la esquina superior izquierda es menor que el valor debajo de la esquina superior izquierda.

Para $2\times4$ el primer enfoque es más eficiente (solo tienes que comparar $2$ valores contra $0$), pero para jardines más grandes el segundo enfoque es más eficiente (siempre solo tienes que comparar $4$ valores para rectángulos, $6$ para cuadrados, independientemente del tamaño del jardín).