How to find the subintervals with zeros

Question

Given a list of 0 and 1,I want to find all the sub-intervals of full zeros. Here is my attempt:

dispo = [0,0,1,1,1,1,0,0,0,0,1,1]

Forbidden_intervals = []
pointer = 0
while pointer < len(dispo):
    length_inter = 0
    for iter in dispo[pointer:]:
        if dispo[iter] ==0:
            length_inter += 1
        else:
            break
    Forbidden_intervals.append((pointer, pointer+length_inter))
    pointer += length_inter + 1

print(Forbidden_intervals)

The expected output is [(0,1),(6,9)] however the current output is [(0,12)]. How to fix it?

score 0 · Answer 1 · answered Oct 28 '20 at 06:55

0

this if line if dispo[iter] == 0 should just be if iter==0 otherwise you're just accessing either element 0 or element 1 in dispo

answered Oct 28 '20 at 06:55

AntiMatterDynamite

1,495
7
17

bereal · Answer 2 · 2020-10-28T07:16:26.280

There are three problems to fix:

if dispo[iter] should be if iter (# 1)
empty subsequences should be ignored (# 2)
if you want the indices of the interval boundaries, fix off-by one error (# 3)
(bonus) iter is not a good variable name, because it shadows the builtin iter function

dispo = [0,0,1,1,1,1,0,0,0,0,1,1]
Forbidden_intervals = []

pointer = 0
while pointer < len(dispo):
    length_inter = 0
    for i in dispo[pointer:]:  # 1
        if i == 0:
            length_inter += 1
        else:
            break
    if length_inter:  # 2
        Forbidden_intervals.append((pointer, pointer+length_inter-1)) # 3
    pointer += length_inter + 1

print(Forbidden_intervals)

That all said, it's not the most efficient way to do this, because of quite many redundant sublist operations. I would implement it with something like a simple finite state machine (with just two states):

dispo = [0,0,1,1,1,1,0,0,0,0,1,1]
forbidden = []

# forbidden_start keeps the index of the ongoing zero sequence start
# or -1 if we're not in a zero sequence
forbidden_start = -1

for i, v in enumerate(dispo):
    if v:
        if forbidden_start >= 0:
           forbidden.append((forbidden_start, i-1))
           forbidden_start = -1

    elif forbidden_start < 0:
         forbidden_start = i

# just in case if the list ends with zeros
if forbidden_start >= 0:
    forbidden.append((forbidden_start, len(dispo)-1))

score 0 · Answer 3 · answered Oct 28 '20 at 08:03

A pretty nice answer can be found here: https://stackoverflow.com/a/20725061/11951277 and adapted to your problem would look like:

dispo = [0,0,1,1,1,1,0,0,0,0,1,1]

zeros = [i for i, d in enumerate(dispo) if d == 0]

ranges = sum((list(t) for t in zip(zeros, zeros[1:]) if t[0]+1 != t[1]), [])

iranges = iter(zeros[0:1] + ranges + zeros[-1:])


print ([(n, next(iranges)) for n in iranges])

How to find the subintervals with zeros

3 Answers3