Multiplicación de matrices por reordenamiento

Tengo una lista de dimensiones de matriz como:

(1, 2), (3, 2), (2, 3), (3, 1)

Quiero reorganizar las dimensiones de la matriz para que todas puedan multiplicarse. Para el anterior, podemos reorganizarlos:

(3, 1), (1, 2), (2, 3), (3, 2)

¿Cómo puedo encontrar esto para una gran cantidad de dimensiones hasta 2000?

Lo he intentado pero next_permutationno C++es eficiente cuando el número de dimensiones es grande.

Solución del problema

Supongamos por simplicidad que para todos los números N, el número de matrices con Nfilas es el mismo que el número de matrices con Ncolumnas. Si este no es el caso, entonces debería faltar exactamente una matriz, de lo contrario no hay solución. Para el ejemplo dado, (2,3)falta una matriz. Simplemente agregue esa matriz faltante. Lo eliminaremos en la etapa final de la solución.

Ahora que hemos satisfecho nuestra condición, las matrices se pueden ordenar en un ciclo. Para nuestro ejemplo, it's (3, 1), (1, 2), (2, 3), (3, 2), (2, 3)y el último se 3conecta con el primero. Nota: sí, como se menciona en los comentarios, este es un ciclo hamiltoniano en un gráfico de conectividad matricial, pero esta clase de gráficos es especial y, de hecho, el problema es más fácil que el problema general del ciclo hamiltoniano. Podemos cortar el ciclo en cualquier parte y esa sería una solución válida (del problema modificado).

Ahora ejecutemos un algoritmo codicioso. Tome cualquier matriz, encuentre cualquier matriz que se pueda multiplicar con ella, luego encuentre otra matriz que se pueda agregar a la cadena, etc. Repita hasta que no haya ninguna matriz que se pueda agregar.

• Afirmación: la cadena resultante se puede cerrar en un ciclo.


• Boceto de prueba: observe el número inicial de la cadena, cuente cuántas veces se incluye en la cadena.

Así que hemos construido un ciclo. Si incluye todas las matrices del conjunto, hemos terminado. Si no, tomamos el conjunto de matrices restantes que no terminaron en el ciclo y resolvemos el problema (es más pequeño que el problema original). Tenga en cuenta que el número de matrices con N filas sigue siendo el mismo que el número de matrices con N columnas en el conjunto restante (porque esto es cierto sobre el conjunto original y es cierto sobre el ciclo recién construido). Ahora tenemos varios ciclos.

Encuentra dos ciclos que tengan una dimensión en común (es decir, hay un fragmento ... N), (N...en ambos ciclos). Corta ambos en ese lugar y únelos para que formen un ciclo más grande. Repita hasta que quede un solo ciclo. Si en algún punto no hay dos ciclos que se puedan unir, no hay solución (cada ciclo representa un componente fuertemente conectado en el gráfico).

Así que ahora tenemos un ciclo que posiblemente contiene una matriz adicional que hemos agregado al principio. Simplemente tiramos esa matriz. Si no hemos añadido nada, podemos cortar el ciclo en un lugar arbitrario.