2

no sabia como ser mas especifico en el titulo, pero el problema es que estoy haciendo un codigo para el problema de isomorfismo de subgrafos (bastante basico la verdad), y tengo un problema, necesito "descomponer" una matriz, con esto me refiero a lo siguiente, tengo esta matriz, por ejemplo:

1.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.0  0.0  0.0  1.0  0.0  0.0  0.0 

Y lo que quiero es que en cada columna y en cada fila quede solamente un uno, por lo que la de arriba, por ejemplo, seria:

1.0  0.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.0  0.0  0.0  1.0  0.0  0.0  0.0 

O bien,

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.0  0.0  0.0  1.0  0.0  0.0  0.0 

Esto necesito para mandar dichas matrices al siguiente paso del problema, la verdad no he tenido muy buenas ideas de como hacerlo. Muchas gracias por su ayuda.

3
  • ¿Con "matriz" te refieres a una construcción con listas anidadas o usas alguna biblioteca externa como NumPy? Lo digo porque el enfoque puede diferir.
    – FJSevilla
    el 2 may. 2018 a las 17:52
  • Para esto estoy usando listas anidadas. el 2 may. 2018 a las 18:01
  • numpy o pandas operan fácilmente sobre matrices
    – Alfabravo
    el 2 may. 2018 a las 20:23

1 respuesta 1

1

Si se tratase de matrices cuadradas la solución podría ser mucho más simple ya que solo se trataría de navegar por la diagonal de la matriz y desde cada posición de esa recta verificar por los 1´s repetidos en la fila y columna completa. Sin embargo al ser matrices rectangulares el trabaja es un poco más complejo y para "navegar" la matriz deberíamos hacer una especie de "zig zag". Hacer este movimiento nos asegura que v

Algo así:

introducir la descripción de la imagen aquí

Con ese "camino" y en cada celda lo que tenemos que hacer es eliminar los 1 redundantes en la fila o columna completa. El código esta bastante crudo y entiendo podría ser mucho mejor, pero al menos funciona. Por otro lado no es muy elegante modificar la misma lista dentro de un ciclo, pero como en este caso solo vamos a modificar los valores, no agregamos ni quitamos elementos, no es tan grave.

import pprint

m = [
      [1.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.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0] 
    ]

# Construyo el camino a recorrer
lpath = len(m) if len(m) >= len(m[0]) else len(m[0])
path = []
r = c = 0
down = right = True
while len(path) < lpath:

  path.append((r,c))

  if (down and r == len(m)-1) or (not down and r == 0):
    down = not down

  if (right and c == len(m[0])-1) or (not right and c == 0):
    right = not right

  r = r + 1 if down else r - 1
  c = c + 1 if right else c - 1

for r,c in path:

  # Borrar 1s por fila
  found = False
  for i in range(len(m[0])):
    m[r][i] = m[r][i] if not found else 0.0
    if m[r][i] == 1.0:
      found = True

  # Borrar 1s por columna
  found = False
  for i in range(len(m)):
    m[i][c] = m[i][c] if not found else 0.0
    if m[i][c] == 1:
      found = True

pprint.pprint(m)

Finalmente

[[1.0, 0.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.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0]]

Editado:

Inicialmente el movimiento en "zig zag" me pareció el más apropiado, para poder asegurarnos que verificamos cada fila y columna. Sin embargo, también podríamos hacer lo siguiente:

introducir la descripción de la imagen aquí

Que se podría resolver de manera más sencilla así:

# Construyo el camino a recorrer
lpath = len(m) if len(m) >= len(m[0]) else len(m[0])
path = []
r = c = 0
while len(path) < lpath:
  path.append((r,c))
  r = r + 1 if r < len(m) - 1 else r
  c = c + 1 if c < len(m[0]) - 1  else c

Nota:

Una penalidad que tiene este algoritmo es que se vuelve a verificar innecesariamente celdas ya verificadas. Una mejora al respecto podría ser manejar un set de filas y columnas ya verificadas y evitarlas.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.