CODEWITHSUNDEEP
pythonlist
user3260982
user3260982

Reputation:

How to check existence of a sequence in a sorted list?

I am having some trouble checking if a sequence exists in a sorted list or not. For example, if my list is 

n=[1,2,3,4,5,6,7]

I can write my code as:

for i in range(1,len(n)):
    if n[i]==n[0]+1:
        print('yes')

But, this logic fails if I am checking 5 numbers at a time. For example, if my list is 

n=[1,3,4,5,6,7,8]

my sequence does not contain the first 5 numbers but it definitely exists in the list. I was wondering if someone could give me some hints about how to check a sequence number by number for 5 numbers at a time. Thanks

Upvotes: 1

Views: 320

Answers (3)

Joohwan
Joohwan

Reputation: 2512

I'm not sure if this is an approach you would like, but using a buffer works.

The idea is you would iterate through your array/list and collect the numbers (in order) until you run into one that is NOT in sequence, where you would dump the contents in the buffer and keep going. If the buffer contains enough numbers at the end you have your sequence.

This way you would only need to iterate the list once and once only O(n).

def check_for_sequence(array, length):
    buf = []
    for n in array:
        if buf == [] or (buf[-1] + 1 == n):
            buf.append(n)
        else:
            buf = [n]

    if len(buf) >= length:
        print buf[:length]
    else:
        print "No sequence of length %s" % length

You can also make this (possibly) faster by terminating the for loop as soon as your buffer hits the required length. But then you'd have to check for the length every iteration.

Upvotes: 0

Ashwini Chaudhary
Ashwini Chaudhary

Reputation: 250881

You can use this recipe from Python2.6's itertools page:

from itertools import groupby
from operator import itemgetter

data = [ 1,  4,5,6, 10, 15,16,17,18, 22, 25,26,27,28,29]
# Find runs of consecutive numbers using groupby.  The key to the solution
# is differencing with a range so that consecutive numbers all appear in
# same group.
for k, g in groupby(enumerate(data), lambda x: x[0]-x[1]):
    seq = list(map(itemgetter(1), g))
    # if you don't want the actual items then:
    # sum(1 for _ in g) >= 5: print('yes') 
    if len(seq) >= 5:
        print (seq)

Output:

[25, 26, 27, 28, 29]

Upvotes: 1

Joran Beasley
Joran Beasley

Reputation: 113940

search_target = [1,2,3,4]
search_space = range(1000)
sub_size = len(search_target)
lists = [search_space[i:i+sub_size] for i in range(len(search_space)-sub_size)]
if search_target in lists:
   print "YUP"

Upvotes: 0

Related Questions