Método para determinar un orden de una matriz de permutación arbitraria

Esto puede parecer una pregunta frecuente (por ejemplo, otra publicación con básicamente el mismo título ), pero estoy interesado en un método para encontrar un orden de una matriz de permutación arbitraria, suponiendo que a veces la matriz es tan grande que no es práctico para inspeccionar las longitudes manualmente.

Esto será, por ejemplo, útil para escribir una función de programación de computadora que tome cualquier matriz de permutación P y escupa el orden de P (es decir, min norte PAG norte = I ).

Un método es un enfoque de fuerza bruta, donde mantenemos aumentar norte hasta que lleguemos PAG norte = I . Sin embargo, me pregunto si hay un método más inteligente.

Su método le permite encontrar el orden de la permutación, pero entonces, ¿cómo obtiene la duración de cada ciclo?
@Yorch, lo siento, confundí 'longitud' y 'orden'. Edité el título y la publicación. Estoy interesado en encontrar el orden de la permutación.

Respuestas (1)

Así es como puede hacerlo, suponga que la matriz es norte × norte .

Obtener la permutación F : { 1 , … , norte } → { 1 , … , norte } dónde F ( j ) es igual a la fila X tal que A X , j = 1 .

Descomponer permutación F en ciclos haciendo una búsqueda sobre el dígrafo con vértices { 1 , … , norte } y bordes i → F ( i ) .

El orden de la matriz es igual a la mcm de todas las longitudes de ciclo.

Algo de código c++:

Esto debería funcionar en O ( norte 2 ) tiempo, ¿verdad? Desde la obtención de la permutación F es O ( norte 2 ) y la descomposición real en ciclos es O ( norte ) ? Solo quiero asegurarme de que entiendo este algoritmo correctamente.
¡Gracias por la explicación y el código de ejemplo! Entonces, este método también encuentra la duración de todos los ciclos, lo que puede ser útil para muchas aplicaciones, aunque puede que no sea más rápido que el método de fuerza bruta mencionado en la publicación (que no identifica todos los ciclos).
El método de fuerza bruta es ridículamente más lento que este método, incluso para matrices de orden 2.
si se necesita O ( norte 2 ) porque tenemos que leer la matriz, pero después de obtener F es O ( norte ) .
@CWC Para mostrar que la fuerza bruta es realmente más lenta, considere que esencialmente tiene que implementar la multiplicación de matrices (aunque puede hacer muchas simplificaciones, conociendo la estructura de las matrices) para hacer esto, y trate de considerar el peor de los casos. complejidad de este tipo de multiplicación repetida
@tolUene Ya veo. No pude considerar la complejidad de las multiplicaciones de matrices. ¡Gracias!
Ahora funciona en todas las permutaciones de grado hasta 6. Iba a mencionar, una entrada como 10 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0requiere 30 multiplicaciones de matriz (alrededor de 30,000 operaciones) en el método de fuerza bruta, pero más como 100 accesos a memoria y solo unas pocas multiplicaciones y restos en tu método.
Método para determinar un orden de una matriz de permutación arbitraria
RespuestasAquíPolítica de privacidad1y, 0v