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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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