Efficient way to find indices of topmost True values in 2d boolean array (Python)

user_16824212 0
Viewed 299

Suppose I have a 2d boolean array with shape (nrows,ncols). I'm trying to efficiently extract the indices of the topmost True value for each column in the array. If the column has all False values, then no indices are returned for that column. Below is an example of a boolean array with shape (4,6) where the indices of the bold Trues would be the desired output.

False False False False False False

True  False False True  False False

True  False True  False False True

True  False True  True  False False

Desired output of indices (row,col): [(1,0),(2,2),(1,3),(2,5)]

I tried using numpy.where and also an implementation of the skyline algorithm but both options are slow. Is there a more efficient way to solve this problem?

Thank you in advance for your help.

boolean python
3 Answers

If you are open to using pandas, you can construct a df, drop columns with False only and then idxmax:

arr = [[False, False, False, False, False, False],
       [True, False, False, True, False, False],
       [True, False, True, False, False, True],
       [True, False, True, True, False, False]]

df = pd.DataFrame(arr, columns=range(len(arr[0])))

s = df.loc[:, df.sum()>0].idxmax()
print (s)

Result:

0    1
2    2
3    1
5    2
dtype: int64

Which is col value vs row value. You can convert it back to your desired form:

print (list(zip(s, s.index)))

[(1, 0), (2, 2), (1, 3), (2, 5)]
user_92844230

You can use np.argmax to detect the first True values.

Prepare the example array.

import numpy as np
a = np.array(
[[0,0,0,0,0,0],
 [1,0,0,1,0,0],
 [1,0,1,0,0,1],
 [1,0,1,1,0,0]]).astype('bool')
a

Output

array([[False, False, False, False, False, False],
       [ True, False, False,  True, False, False],
       [ True, False,  True, False, False,  True],
       [ True, False,  True,  True, False, False]])

Stack one row of False to deal with columns without a True. Find first True in every column with np.argmax and append an arange for the row indices. You have to adjust the column indices by -1 because we added one row to the array. Then select the columns where the True's index was greater than 0

b = np.vstack([np.zeros_like(a[0]),a])
t = b.argmax(axis=0)
np.vstack([t - 1, np.arange(len(a[0]))]).T[t > 0]

Output

array([[1, 0],
       [2, 2],
       [1, 3],
       [2, 5]])

Translating @HenryYik answer to numpy gives a one line solution

np.vstack([a.argmax(axis=0), np.arange(len(a[0]))]).T[a.sum(0) > 0]

Output

array([[1, 0],
       [2, 2],
       [1, 3],
       [2, 5]])
user_142777220

I suggest you try this:

def get_topmost(ar: np.ndarray):
    return [(row.index(True), i) for i, row in enumerate(ar.T.tolist()) if True in row]

Example: (should works as is)

>>> test = np.array([
    [False, False, False, False, False, False],
    [True,  False, False, True,  False, False],
    [True,  False, True,  False, False, True],
    [True,  False, True,  True,  False, False],
])

>>> print(get_topmost(test))
[(1, 0), (2, 2), (1, 3), (2, 5)]
user_155152060
Related