How to remove specific elements within a matrix in Python?

Question

How to remove specific elements within a matrix in Python?

Navigation

#1 by (1 votes)

2

I did not know how to be more specific in the title, but the problem is that I'm doing a code for the problem of isomorphism of subgraphs (quite basic the truth), and I have a problem, I need to "decompose" a matrix, with this I mean the following, I have this matrix, for example:

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

And what I want is that in each column and in each row there is only one, so the one above, for example, would be:

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

Or,

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

This I need to send these matrices to the next step of the problem, the truth I have not had very good ideas on how to do it. Thank you very much for your help.

python matrices graphql

asked by Santiago Pozo Ruiz 02.05.2018 в 18:44

source

1 answer

How to read a JSON response from AJAX? Mouseover and mouseout event in JavaScript

score 1 · Answer 1

If it were square matrices the solution could be much simpler since it would only be to navigate the diagonal of the matrix and from each position of that line to check for the 1's repeated in the row and full column. However, being rectangular matrices the work is a bit more complex and to "navigate" the matrix we should make a kind of "zig zag". Making this move assures us that v

Something like this:

With that "path" and in each cell what we have to do is eliminate the redundant 1 in the row or entire column. The code is pretty crude and I understand it could be much better, but at least it works. On the other hand it is not very elegant to modify the same list within a cycle, but as in this case we are only going to modify the values, we do not add or remove elements, it is not so serious.

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)

Finally

[[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]]

Edited:

Initially the movement in "zig zag" seemed the most appropriate, to be able to make sure that we verified each row and column. However, we could also do the following:

What could be resolved more simply like this:

# 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

Note:

One penalty that this algorithm has is that cells already verified are unnecessarily verified again. An improvement in this regard could be to manage a set of already verified rows and columns and avoid them.