[SOLUCIONADO] Permutacion MAX en matrices

[Macas]

Muy buenas,

Necesito implementar un programailla que permutando filas y columnas de una matriz me encuentre unas letras en un diccionario.

Tengo la aplicacion echa pero no me encuentra las matrices que busco, bueno algunas si.

Tengo entendido que en un array el numero de combinaciones es n! y en una matriz n! * n!, siempre y cuando siempre hagas permutaciones de filas y columnas es asi?

Si tengo una 4x4, el numero max de permutaciones es 4!*4!?

Lo que tengo que hacer el graph matching, alguien sabe de algun algoritmo entendible, he buscado pero no encuentro nada de ayuda.

Saludos

[razpeitia]

En cuanto a las permutaciones de filas y columnas de una matriz puedes hacerlo de esta manera:

Código Python:

from itertools import permutations
 
def matrix_perms(rows, cols):
    for i in permutations(range(rows)):
        for j in permutations(range(cols)):
            yield (i, j)
for rows, cols in matrix_perms(4, 4):
    print rows, cols
 

Lo cual te da: 576 = 24 * 24 = 4! * 4!

Obviamente el chiste aquí es el primer elemento del la lista ahora va a ser tu indice 0, el segundo el indice 1 y así sucesivamente.

Ejemplo:

Código Python:

from itertools import permutations
 
def matrix_perms(rows, cols):
    for i in permutations(range(rows)):
        for j in permutations(range(cols)):
            yield (i, j)
 
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for rows, cols in matrix_perms(3, 3):
    for row in rows:
        for col in cols:
            print matrix[row][col],
        print
    print
 

Hay vídeos en youtube sobre Maximum Matching, en caso que leer la wikipedia sea un poco difícil http://en.wikipedia.org/wiki/Matching_(graph_theory)