Finding a change in a row of a matrix in python

Question

I have a NxM matrix encoded in 0s and 1s - where only the 1s are to be printed in its respective locations whereas the 0s are blank spaces, such as the following matrix:

 m = [[0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0]
      [0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0]
      [0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0]
      [0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0]
      [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0]
      [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0]
      [1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1]

My question is how can I create a starting point from the change that takes place from a 0 to a 1 and an end point from the change that takes place from a 1 to a 0 in each row. Then print all the 1s between the start point and end point

I have the following code (which does not work):

nrows, ncols = m.shape #gets the shape of the matrix
for r in range(nrows):
  for c in range(ncols):
    if m[r,c] == 0 and m[r,c+1] == 1: #checks if there is a 0 first and then a 1 in the next index of the column in the row to create a starting point
       start = m[r,c+1]
    if m[r,c] == 1 and m[r,c+1] == 0: #checks if there is a 1 first and then a 0 in the next index of the column in the row to create an end point
       end = m[r, c+1]

My desired output is, for example taking the lastrow into consideration:

It should print everything between the first 1 and last 1 before a 0 is found in that row, excluding the 0s. So basically this: 1 1 1 1....1 1 1 1 1 1....1 1 The dots (.)represent the 0s that have to be excluded All help and advice will be highly appreciated.

Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. "It doesn't work" is not a problem specification. — Prune, May 19 '17 at 16:18
@not_a_robot asks a very important question: what are you expecting as the result of your function? It's not clear. You've been thinking about this for some time, and for you it's intuitive, but we just got the news =) — salezica, May 19 '17 at 16:23
@not_a_robot I have edited the question with the desired output that I require - my apologies for a vaguely asked question. Basically, I need to group all the 1s in each row. — Pratham Patel, May 19 '17 at 16:43
I still am having trouble understanding the desired output. As stated, why wouldn't you just iterate through the matrix printing the element or "." if the element is 0? — Jared Goguen, May 19 '17 at 17:01

score 1 · Accepted Answer · edited May 23 '17 at 12:18

1

Is your goal the printed output or is your goal the markers that indicate where 1's begin and end? If your goal is just the printed output, why not something simple like:

m = [[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0],
     [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1]
]

for row in m:
    for bit in row:
        print(bit or ' ', end=' ')
    print()

OUTPUT

              1 1 1 1                   
              1 1 1 1                   
          1 1 1 1                       
          1 1 1 1                       
                            1 1 1 1     
                            1 1 1 1     
1 1 1 1         1 1 1 1 1 1         1 1

Manipulate as you see fit to eliminate the spaces for the zeros or spaces between the 1's (i.e. ' ' space vs. '' empty string.)

Do you mind showing/explaining on how I am able to get the markers where the 1s begin and end?

Borrowing from an SO answer to Identify groups of continuous numbers in a list, we can do:

for row in m:
    indicies = compress(count(), row)

    ranges = []

    for _, g in groupby(enumerate(indicies), lambda x: x[0] - x[1]):
        group = [x[1] for x in g]
        ranges.append((group[0], group[-1]))

    print(ranges)

OUTPUT

[(7, 10)]
[(7, 10)]
[(5, 8)]
[(5, 8)]
[(14, 17)]
[(14, 17)]
[(0, 3), (8, 13), (18, 19)]

edited May 23 '17 at 12:18

Community

1
1

answered May 19 '17 at 17:03

cdlane

40,441
5
32
81

This answers the question as stated, I'm just having trouble believing that this is the actual question. – Jared Goguen May 19 '17 at 17:04
1

Also, `bit or ' '` might be more concise than `bit if bit else ' '` – Jared Goguen May 19 '17 at 17:10
1

@JaredGoguen agreed and thanks! I plan to hold off on any edits until we get feedback from the OP about what's really desired. – cdlane May 19 '17 at 17:13
@cdlane Thank you so much, this is exactly what I want. Thank you so much. – Pratham Patel May 19 '17 at 18:33
My initial goal was to determine where the 1s begin and end in every row, but this also helps quite a lot – Pratham Patel May 19 '17 at 18:40
@cdlane From your code example, I did try to get where the 1s begin and end in each row, but I was unable to do so. Do you mind showing/explaining on how I am able to get the markers where the 1s begin and end? – Pratham Patel May 19 '17 at 20:15
@PrathamPatel, no the solution I provided was clearly prefixed with, "If your goal is just the printed output" -- it does not provide the markers. If I were to provide such code, in what format do you want the markers? – cdlane May 19 '17 at 20:25
@cdlane Ooh I see, the format of the markers can be in - [row, column] notation. Thank you so much once again. – Pratham Patel May 19 '17 at 20:36
@cdlane My apologies, but I have one last question - I have a painter function (`painter.paint('line', start_row, start_col, end_row, end_col)` -start_row and end_row is row and start_col and end_col is group[0] and group[-1] ) that should print the pixels between the starting point and end point of the 1s (as you showed me above), however, when I use it in the function, I get the following error `TypeError: only length-1 arrays can be converted to Python scalars`. Any advice on how I can perhaps fix that? – Pratham Patel May 20 '17 at 23:55
@PrathamPatel, if you're still having a problem with your `paint()` method, I suggest you post such as a new question with a pointer back to this question for additional context. – cdlane May 25 '17 at 21:05
@cdlane No problem, I did manage to sort the problem I had out, your code helped the most - thanks so much. – Pratham Patel May 26 '17 at 16:38

score 0 · Answer 2 · answered May 19 '17 at 16:33

You haven't given a viable MCVE yet; I converted this to Python and made a solution.

You take each row, shift it left one position, and subtract from the original. This will mark all transitions with 1 and -1. Then you just need to find the first 0=>1 change, and then the 1=>0 change after that. Adjust the indices as you see fit.

Note: I kept this low-tech. The solution can be greatly shortened if you convert the lists to bitmaps, find transitions with XOR, and be careful about marking the starting value (if it starts with 1, then you need the 2nd & 3rd transitions, not the first two).

m = [[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0],
     [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1]
]

for row in range(len(m)):
    line = m[row]
    first = line[:-1]
    shift = line[1:]

    diff = [first[i] - shift[i] for i in range(len(first))]
    l_bound = diff.index(-1) + 1
    r_bound = diff[l_bound:].index(1) + l_bound
    print
    print row, '\t', line
    print '\t', diff
    print '\t', l_bound, r_bound

Output:

0   [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
    7 10

1   [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
    7 10

2   [0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    5 8

3   [0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    5 8

4   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0]
    14 17

5   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0]
    14 17

6   [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1]
    [0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1, 0]
    8 13

If I take a look at line 6 in the output for example, why does it not print the other bounds of the same row? — Pratham Patel, May 21 '17 at 06:53
The first set of 1's has no 0=>1 transition; the second set has no 1=> transition. The posting specified both endpoints, and a *singular* string of 1's in each row. I wrote my solution to those phrases. — Prune, May 22 '17 at 15:54

score 0 · Answer 3 · answered May 19 '17 at 16:54

Here's a straight forward way of getting the successive differences into a new array.

coded = np.append(m[:,:1]*2-1, m[:,1:] - m[:,:-1], axis=1)
# [[-1  0  0  0  0  0  0  1  0  0  0 -1  0  0  0  0  0  0  0  0]
#  [-1  0  0  0  0  0  0  1  0  0  0 -1  0  0  0  0  0  0  0  0]
#  [-1  0  0  0  0  1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0]
#  [-1  0  0  0  0  1  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  0  0  0  1  0  0  0 -1  0]
#  [-1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0 -1  0]
#  [ 1  0  0  0 -1  0  0  0  1  0  0  0  0  0 -1  0  0  0  1  0]]

In this array, a -1 indicates the start of a spree of 0's, and a 1 indicates the start of a spree of 1's. I'm not exactly clear on what you're trying to do, but maybe this will help.

Finding a change in a row of a matrix in python

3 Answers3