CODEWITHSUNDEEP
pythonlistpython-2.7sequence
Евгений Речков
Евгений Речков

Reputation: 339

How to find defined sequence in the list?

For example I have list with events: 

list = ['A','B','A','A','B','B','A'...]

I need to find sequence of events for example 'B','A','A' to check if its exists or not If yes - how many times it's present in list.

For current list output should be: 

Exists: 1 times

Upvotes: 2

Views: 128

Answers (4)

GingerPlusPlus
GingerPlusPlus

Reputation: 5606

If you have a way to turn you list into string, you can use str.count:

lst = ['A','B','A','A','B','B','A']

to_str = ''.join

print "Exists: %d times" % to_str(lst).count(to_str(['B','A','A']))

Upvotes: 1

Sede
Sede

Reputation: 61225

You can use regular expressions

>>> import re
>>> l = ['A','B','A','A','B','B','A']
>>> pat = re.compile(r'BAA')
>>> sequences = pat.findall(''.join(l))
>>> sequences
['BAA']
>>> len(sequences)
1
>>>

But the best way to do this is using a generator function:

>>> def find_sequences(sequences, events):
...     i = 0
...     events_len = len(events)
...     sequences_len = len(sequences)
...     while i < sequences_len:
...             if sequences[i:i+events_len] == events: 
...                 yield True
...             i = i + 1
... 
>>> list(find_sequences(lst, events))
>>> sum(find_sequences(['AB', 'A', 'BA', 'A', 'BA'], ['A', 'BA']))
2

Upvotes: 1

user2390182
user2390182

Reputation: 73450

Using sorted suffix array and binary search:

from bisect import bisect_left

# returns insertion index
def binary_search(seq, el, lo=0, hi=None):
    hi = hi if hi is not None else len(seq)
    pos = bisect_left(seq, el, lo, hi)
    return pos

def subSequenceCount(sequence, subSequence):
    suffixes = []
    for start in range(len(sequence)-1):
        suffixes.append(sequence[start:])
    suffixes.sort()
    insertPos = binary_search(suffixes, subSequence)
    count = 0
    while insertPos < len(suffixes) and suffixes[insertPos][:len(subSequence)] == subSequence:
        count += 1
        insertPos += 1
    return count

Upvotes: 2

Mike M&#252;ller
Mike M&#252;ller

Reputation: 85432

As an exercise of looping and list slicing:

events = ['A','B','A','A','B','B','A','A']
target = ['B', 'A', 'A']

size = len(target)
count = 0
for start in range(len(events) - size + 1):
    if events[start:start + size] == target:
        count += 1

Or with a list comprehension:

events = ['A','B','A','A','B','B','A','A']
target = ['B', 'A', 'A']

size = len(target)
count = len([start for start in range(len(events) - size + 1) 
             if events[start:start + size] == target])

Upvotes: 2

Related Questions