Count the number of tails since the last head

Question

Consider the sequence of moments: 1, 0, 0, 1, 0, 1, where tail = 0 and head = 1.

The required output is the sequence: 0, 1, 2, 0, 1, 0

Each element of the output sequence counts the number of tails from the last chapter.

I tried the naive method:

def timer(seq): if seq[0] == 1: time = [0] if seq[0] == 0: time = [1] for x in seq[1:]: if x == 0: time.append(time[-1] + 1) if x == 1: time.append(0) return time 

Question : Is there a better way?

Answer 1

Using NumPy:

 import numpy as np seq = np.array([1,0,0,1,0,1,0,0,0,0,1,0]) arr = np.arange(len(seq)) result = arr - np.maximum.accumulate(arr * seq) print(result) 

gives

 [0 1 2 0 1 0 1 2 3 4 0 1] 

---

Why is arr - np.maximum.accumulate(arr * seq) ? The desired result seemed to be related to a simple progression of integers:

 arr = np.arange(len(seq)) 

So, the natural question is: if seq = np.array([1, 0, 0, 1, 0, 1]) and the expected result is expected = np.array([0, 1, 2, 0, 1, 0]) , then what value does x do

 arr + x = expected 

WITH

 In [220]: expected - arr Out[220]: array([ 0, 0, 0, -3, -3, -5]) 

it looks like x should be the cumulative maximum of arr * seq :

 In [234]: arr * seq Out[234]: array([0, 0, 0, 3, 0, 5]) In [235]: np.maximum.accumulate(arr * seq) Out[235]: array([0, 0, 0, 3, 3, 5]) 

Answer 2

Step 1: Invert l :

 In [311]: l = [1, 0, 0, 1, 0, 1] In [312]: out = [int(not i) for i in l]; out Out[312]: [0, 1, 1, 0, 1, 0] 

Step 2: list comp; add the previous value to the current value if the current value is 1.

 In [319]: [out[0]] + [x + y if y else y for x, y in zip(out[:-1], out[1:])] Out[319]: [0, 1, 2, 0, 1, 0] 

This eliminates windy ifs by shifting neighboring elements.

Answer 3

Using itertools.accumulate :

 >>> a = [1, 0, 0, 1, 0, 1] >>> b = [1 - x for x in a] >>> list(accumulate(b, lambda total,e: total+1 if e==1 else 0)) [0, 1, 2, 0, 1, 0] 

accumulate defined only in Python 3. There is equivalent Python code in the above documentation, however, if you want to use it in Python 2.

It is required to invert a , because the first element returned by accumulate is the first element of the list, regardless of the battery function:

 >>> list(accumulate(a, lambda total,e: 0)) [1, 0, 0, 0, 0, 0] 

Answer 4

The required output is an array with the same length as the input, and none of the values ​​are equal to the input. Therefore, the algorithm must be at least O (n) in order to form a new output array. In addition, for this particular problem, you will also need to scan all the values ​​for the input array. All of these operations are O (n), and they will not be more efficient. The constants may vary, but your method is already in O (n) and will not be less.

Answer 5

Using reduce :

time = reduce(lambda l, r: l + [(l[-1]+1)*(not r)], seq, [0])[1:]

Answer 6

I try to be clear in the following code and differ from the original when using an explicit battery.

 >>> s = [1,0,0,1,0,1,0,0,0,0,1,0] >>> def zero_run_length_or_zero(seq): "Return the run length of zeroes so far in the sequnece or zero" accumulator, answer = 0, [] for item in seq: accumulator = 0 if item == 1 else accumulator + 1 answer.append(accumulator) return answer >>> zero_run_length_or_zero(s) [0, 1, 2, 0, 1, 0, 1, 2, 3, 4, 0, 1] >>>