Pythonic way to determine whether not null list en

Question

I'm looking for a way to easily determine if all not None items in a list occur in a single continuous slice. I'll use integers as examples of not None items.

For example, the list [None, None, 1, 2, 3, None, None] meets my requirements for continuous integer entries. By contrast, [1, 2, None, None, 3, None] is not continuous, because there are None entries between integers.

Some more examples to make this a clear as possible.

Continuous:
[1, 2, 3, None, None]
[None, None, 1, 2, 3]
[None, 1, 2, 3, None]

Not Continuous:
[None, 1, None, 2, None, 3]
[None, None, 1, None, 2, 3]
[1, 2, None, 3, None, None]

My first approach was to use variables to keep track of whether or not we had come across a None yet, and whether or not we had come across an int yet -- this ends up with a highly nested and very difficult to follow series of if/else statements embedded in a for loop. (On top of the ugliness, I confess I haven't gotten it to work in every case).

Anyone know an easier way to figure out if the not None items in a list occur in a single continuous slice?

Answer 1

This may not be the best way to go about doing it, but you can look for the first non-None entry and the last non-None entry and then check the slice for None. e.g.:

def is_continuous(seq):
    try:
        first_none_pos = next(i for i,x in enumerate(seq) if x is not None)
        #need the or None on the next line to handle the case where the last index is `None`.
        last_none_pos = -next(i for i,x in enumerate(reversed(seq)) if x is not None) or None
    except StopIteration: #list entirely of `Nones`
        return False
    return None not in seq[first_none_pos:last_none_pos]

assert is_continuous([1,2,3,None,None]) == True
assert is_continuous([None, 1,2,3,None]) == True
assert is_continuous([None, None, 1,2,3]) == True
assert is_continuous([None, 1, None, 2,3]) == False
assert is_continuous([None, None, 1, None, 2,3]) == False
assert is_continuous([None, 1, None, 2, None, 3]) == False
assert is_continuous([1, 2, None, 3, None, None]) == False

This will work for any sequence type.

Answer 2

This algorithm does the work with a few drawbacks (it removes items form the list). But it's a solution.

Basically if you remove all continuous None from start and the end. And if you found some None in the list then the integers are not in a continuous form.

def is_continuous(seq):
    while seq and seq[0] is None: del seq[0]
    while seq and seq[-1] is None: del seq[-1]

    return None not in seq

assert is_continuous([1,2,3,None,None]) == True
assert is_continuous([None, 1,2,3,None]) == True
assert is_continuous([None, None, 1,2,3]) == True
assert is_continuous([None, 1, None, 2,3]) == False
assert is_continuous([None, None, 1, None, 2,3]) == False
assert is_continuous([None, 1, None, 2, None, 3]) == False
assert is_continuous([1, 2, None, 3, None, None]) == False

Yet, another example of how small code could become evil.

I wish a strip() method were available for list.

Answer 3

def contiguous(seq):
    seq = iter(seq)
    all(x is None for x in seq)        # Burn through any Nones at the beginning
    any(x is None for x in seq)        # and the first group
    return all(x is None for x in seq) # everthing else (if any) should be None.

Here are a couple of examples. You can use next(seq) to get the next item from an iterator. I'll put a mark pointing to the next item after each

example1:

seq = iter([None, 1, 2, 3, None])        #  [None, 1, 2, 3, None]
                                         # next^
all(x is None for x in seq)            
                                         #        next^
any(x is None for x in seq)            
                                         #                    next^ (off the end)
return all(x is None for x in seq)       # all returns True for the empty sequence

example2:

seq = iter([1, 2, None, 3, None, None])  #    [1, 2, None, 3, None, None]
                                         # next^
all(x is None for x in seq)            
                                         #    next^
any(x is None for x in seq)            
                                         #             next^  
return all(x is None for x in seq)       # all returns False when 3 is encountered

Answer 4

One liner:

contiguous = lambda l: ' ' not in ''.join('x '[x is None] for x in l).strip()

The real work is done by the strip function. If there are spaces in a stripped string, then they're not leading/trailing. The rest of the function converts the list to a string, which has a space for each None.

Answer 5

My first approach was to use variables to keep track ...

...this ends up with a highly nested and very difficult to follow series of if/else statements embedded in a for loop...

No! Actually you need only one variable. Thinking this problem in the view of Finite State Machine(FSM) with your approach will lead to a quite nice solution.

We call the state p. At first, p is 0. Then we start walking between the states.

When all the elements in the list is examinated and still don't fail then the answer is True.

One version that encode the translation table in a dict

def contiguous(s, _D={(0,0):0, (0,1):1, (1,0):2, (1,1):1, (2,0):2, (2,1):3}):
    p = 0
    for x in s:
        p = _D[p, int(x is not None)]
        if p >= 3: return False
    return True

Another version that use if statement:

def contiguous(s):
    p = 0
    for x in s:
        if x is None and p == 1 or x is not None and (p == 0 or p == 2):
            p += 1
        if p >= 3: return False
    return True

So my point is that using if and for are still pythonic.

update

I found another way to encode the FSM. We can pack the translation table into a 12bit integer.

def contiguous(s):
    p = 0
    for x in s:
        p = (3684 >> (4*p + 2*(x!=None))) & 3
        if p >= 3: return False
    return True

Here 3684, the magic number, can be obtained by:

    _D[p,a]     3  2  1  2  1  0
         p      2  2  1  1  0  0
         a      1  0  1  0  1  0
bin(3684) = 0b 11 10 01 10 01 00 

The readability is not as good as other version but it's faster since it avoids dictionary lookup. The second version is as fast as this but this encoding idea can be generalized to solve more problems.

Answer 6

You could use something like itertools.groupby:

from itertools import groupby

def are_continuous(items):
    saw_group = False

    for group, values in groupby(items, lambda i: i is not None):
        if group:
            if saw_group:
                return False
            else:
                saw_group = True

    return True

This will iterate only until it sees a group twice. I'm not sure if you consider [None, None], so tweak it to your needs.