CODEWITHSUNDEEP
pythonnumpy
Duncan Macleod
Duncan Macleod

Reputation: 1065

How can I tell whether a numpy boolean array contains only a single block of `True`s?

If I have a numpy array containing booleans, say the output of some math comparison, what's the best way of determining whether that array contains only a single contiguous block of Trues, e.g.

array([False, False, False, True, True, True, False, False, False], dtype=bool)

i.e. where the sequence ...,True, False, ..., True... never occurs?

Upvotes: 8

Views: 3293

Answers (4)

Bi Rico
Bi Rico

Reputation: 25813

If you only have a single block of Trues, that means you either have one transition in the array or you have two transitions and the array starts and ends with False. Also there is the trivial case where the whole array is True. So you could do something like:

def singleBlockTrue(array):
   if len(array) == 0:
       return False
   transitions = (array[1:] != array[:-1]).sum()
   if transitions == 0:
       return array[0]
   if transitions == 1:
       return True
   if transitions == 2:
       return not array[0]
   return False

This is effectively the same logic, but the code is a little cleaner.

def singleBlockTrue(array):
    if len(array) == 0:
        return False
    transitions = (array[1:] != array[:-1]).sum()
    transitions = transitions + array[0] + array[-1]
    return transitions == 2

Some timeings related to the comments:

In [41]: a = np.zeros(1000000, dtype=bool)

In [42]: timeit a[:-1] != a[1:]
100 loops, best of 3: 2.93 ms per loop

In [43]: timeit np.diff(a.view('uint8'))
100 loops, best of 3: 2.45 ms per loop

In [44]: timeit np.diff(a.astype('uint8'))
100 loops, best of 3: 3.41 ms per loop

In [45]: timeit np.diff(np.array(a, 'uint8'))
100 loops, best of 3: 3.42 ms per loop

Upvotes: 1

Jon Clements
Jon Clements

Reputation: 142106

Not a numpy native approach, but you can use itertools.groupby to reduce blocks of continuous values into a single item, and then check that only a truthy value appears once using any. Since grouped is an iterable the first any returns True as soon as a truthy value is found, you then resume the check on the remainder of the iterable and make sure there is not another truthy value.

from itertools import groupby

def has_single_true_block(sequence):
    grouped = (k for k, g in groupby(sequence))
    has_true = any(grouped)
    has_another_true = any(grouped)
    return has_true and not has_another_true

Upvotes: 3

mVChr
mVChr

Reputation: 50167

import numpy as np

def has_single_true_block(arr):
    if not len(arr):
        return False
    blocks = len(np.array_split(arr, np.where(np.diff(arr) != 0)[0] + 1))
    if blocks > 3:
        return False
    elif blocks == 3 and arr[0] and arr[-1]:
        return False
    elif blocks == 1 and not arr[0]:  # 0 True blocks
        return False
    return True

# TESTS

a1 = np.array([False, False, True, True, True, False, False], dtype=bool)
has_single_true_block(a1)  # => True

a2 = np.array([True, True, False, False], dtype=bool)
has_single_true_block(a2)  # => True

a3 = np.array([False, False, True, True], dtype=bool)
has_single_true_block(a3)  # => True

f1 = np.array([False, False, True, False, True, False, False], dtype=bool)
has_single_true_block(f1)  # => False

f2 = np.array([True, True, False, False, True, True], dtype=bool)
has_single_true_block(f2)  # => False

f3 = np.array([False, False, False], dtype=bool)
has_single_true_block(f3)  # => False

Upvotes: 1

shx2
shx2

Reputation: 64298

numpy.diff is useful in this case. You can count the number of -1's in the diffed array.

Note, you'd also need to check the last element -- if it's True, there wouldn't be a -1 in the diffed array to indicate that. Better yet, you can append False to the array before diffing.

import numpy as np
a = np.array([False, False, False, True, True, True, False, False, False], dtype=bool)
d = np.diff(np.asarray(a, dtype=int))
d
=> array([ 0,  0,  1,  0,  0, -1,  0,  0])
(d < 0).sum()
=> 1

To append False at the end:

b = np.append(a, [ False ])
d = np.diff(np.asarray(b, dtype=int))
...

Now, "the sequence ...,True, False, ..., True... never occurs" iff (d<0).sum() < 2.

A trick to avoid the append operation (and make your code more obscure) is by doing: (d<0).sum() + a[-1] < 2 (i.e., if a[-1] is True, count it as a block). This would only work if a is not empty, of course.

Upvotes: 6

Related Questions