Python: Extracting lists from list with module or regular expression

Question

I'm trying to extract lists/sublists from one bigger integer-list with Python2.7 by using start- and end-patterns. I would like to do it with a function, but I cant find a library, algorithm or a regular expression for solving this problem.

def myFunctionForSublists(data, startSequence, endSequence):
    # ... todo

data = [99, 99, 1, 2, 3, 99, 99, 99, 4, 5, 6, 99, 99, 1, 2, 3, 99, 4, 5, 6, 99]

startSequence = [1,2,3]
endSequence = [4,5,6]

sublists = myFunctionForSublists(data, startSequence, endSequence)

print sublists[0] # [1, 2, 3, 99, 99, 99, 4, 5, 6]
print sublists[1] # [1, 2, 3, 99, 4, 5, 6]

Any ideas how I can realize it?

Answer 1

Here's a more general solution that doesn't require the lists being sliceable, so you can use it on other iterables, like generators.

We keep a deque the size of the start sequence until we come across it. Then we add those values to a list, and keep iterating over the sequence. As we do, we keep a deque the size of the end sequence, until we see it, also adding the elements to the list we're keeping. If we come across the end sequence, we yield that list and set the deque up to scan for the next start sequence.

from collections import deque

def gen(l, start, stop):
    start_deque = deque(start)
    end_deque = deque(stop)
    curr_deque = deque(maxlen=len(start))
    it = iter(l)
    for c in it:
        curr_deque.append(c)
        if curr_deque == start_deque:
            potential = list(curr_deque)
            curr_deque = deque(maxlen=len(stop))
            for c in it:
                potential.append(c)
                curr_deque.append(c)
                if curr_deque == end_deque:
                    yield potential
                    curr_deque = deque(maxlen=len(start))
                    break

print(list(gen([99, 99, 1, 2, 3, 99, 99, 99, 4, 5, 6, 99, 99, 1, 2, 3, 99, 4, 5, 6, 99], [1,2,3], [4,5,6])))

# [[1, 2, 3, 99, 99, 99, 4, 5, 6], [1, 2, 3, 99, 4, 5, 6]]

Answer 2

Here is an itertools approach that uses a collections.deque of limited length to keep a buffer of the last elements of appropriate size. It assumes that your sublists don't overlap and that your start and end sequences don't overlap either.

It works for any sequence for data, start, end (even generators).

from collections import deque
from itertools import islice

def sublists(data, start, end):
    it = iter(data)
    start, end = deque(start), deque(end)
    while True:
        x = deque(islice(it, len(start)), len(start))
        # move forward until start is found
        while x != start:
            x.append(next(it))
        out = list(x)
        x = deque(islice(it, len(end)), len(end))
        # move forward until end is found, storing the sublist
        while x != end:
            out.append(x[0])
            x.append(next(it))
        out.extend(end)
        yield out

data = [99, 99, 1, 2, 3, 99, 99, 99, 4, 5, 6, 99, 99, 1, 2, 3, 99, 4, 5, 6, 99]

startSequence = [1,2,3]
endSequence = [4,5,6]

print(list(sublists(data, startSequence, endSequence)))
# [[1, 2, 3, 99, 99, 99, 4, 5, 6], [1, 2, 3, 99, 4, 5, 6]]

Answer 3

If you really want to use regular expressions, you can change the lists of integers to strings and use the regex that way

import re

def find_span(numbers, start, end):
    # Create strings from the start and end lists.
    start_pattern = ''.join(map(chr, start))
    end_pattern = ''.join(map(chr, end))

    # convert the list to search into one string.
    s = ''.join(map(chr, numbers))

    # Create a pattern that starts and ends with the correct sublists,
    # and match all sublists. Then convert each match back to a list of
    # integers
    # The '?' is to make the regex non-greedy
    return [
        [ord(c) for c in match]
        for match in re.findall(rf'{start_pattern}.*?{end_pattern}', s, re.DOTALL)
    ]

>>> find_span(search, start, end)  # Using OP's sample values
[[1, 2, 3, 99, 99, 99, 4, 5, 6], [1, 2, 3, 99, 4, 5, 6]]

Note this is not really efficient, since it requires dynamically building a regex each time it's called. And you need to use re.DOTALL because otherwise it won't match anything containing 10 (which is the ascii encoding of newline). However, if you really want to use regexes, this would work.

Answer 4

Just iterate all in indices in the list and compare the slice to the startSequence or the endSequence, respectively. Assuming that the sublists are not supposed to overlap, you can use the same iterator for both loops.

def myFunctionForSublists(data, startSequence, endSequence):
    positions = iter(range(len(data)))
    for start in positions:
        if data[start:start+len(startSequence)] == startSequence:
            for end in positions:
                if data[end:end+len(endSequence)] == endSequence:
                    yield data[start:end+len(endSequence)]
                    break

This way, the start loop will continue where the end loop left. If they can overlap, use two separate iterators for the loop, i.e. for start in range(len(data)): and for end in range(start+1, len(data)):

Answer 5

Use below method:

def find_sub_list(sl,l):
    sll=len(sl)
    for ind in (i for i,e in enumerate(l) if e==sl[0]):
        if l[ind:ind+sll]==sl:
            return ind,ind+sll-1

find_sub_list([1,2,3], data)    
>>>(2, 4)
find_sub_list([4,5,6], data)    
>>>(8, 10)

data[2:10+1]
>>>[1, 2, 3, 99, 99, 99, 4, 5, 6]

You can follow similar approach for sublists[1]

Courtesy : find-starting-and-ending-indices-of-sublist-in-list

Answer 6

Here is a O(n) solution that finds matches by keeping track of matching patterns of startSequence and endSequence

def myFunctionForSublists(data, startSequence, endSequence):
    start,end = tuple(startSequence), tuple(endSequence)
    l1, l2    = len(start), len(end)
    s = -1
    result = []
    for i,v in enumerate(zip(*[data[i:] for i in range(0,l1)])):
        if v == start:
            s = i
        if v == end and s != -1:
            result.append(data[s:i+l2])
            s = -1

    return result


print (myFunctionForSublists(data, startSequence, endSequence))
# [[1, 2, 3, 99, 99, 99, 4, 5, 6], [1, 2, 3, 99, 4, 5, 6]]