Find sub list inside a list in python

Question

I have a list of numbers

l = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 2, 1, 1, 2, 0, 0, 0, 0]
[0, 0, 2, 1, 1, 2, 2, 0, 0, 1]
[0, 0, 1, 2, 2, 0, 1, 0, 0, 2]
[1, 0, 1, 1, 1, 2, 1, 0, 2, 1]]

For example , i have to search a pattern '2,1,1,2' , as we can see that is present in row 6 and 7 . in order to find that sequence i tried converting each list into str and tried to search the pattern , but for some reason the code isnt working.

import re
for i in l:
 if re.search('2,1,1,2' , str(i).strip('[').strip(']')): print " pattern found"

am i missing something in here ?

See http://stackoverflow.com/questions/3313590/check-for-presence-of-a-sublist-in-python for a very similar question. — Petr Viktorin, Oct 02 '11 at 16:27

score 7 · Accepted Answer · answered Oct 02 '11 at 16:26

7

Converting your list in string is really not a good idea.

How about something like this:

def getsubidx(x, y):
    l1, l2 = len(x), len(y)
    for i in range(l1):
        if x[i:i+l2] == y:
            return i

answered Oct 02 '11 at 16:26

cJ Zougloub

1,484
10
19

actually the list l has many list as its elements. and converting into string allows me to use reg expressions. but if there is any computational efficiency in this method , then why not ! – Rahul Oct 02 '11 at 16:39
+1, regex is really overkill for this problem. Simply looking to see if a sublist matches the query list should be way more efficient. – MAK Oct 02 '11 at 17:03
well i m kinda very used to reg expressions . Still getting acquainted to pythonic way of coding. – Rahul Oct 02 '11 at 17:54

score 2 · Answer 2 · answered Jan 24 '13 at 09:04

2

I suggest you to use the Knuth-Morris-Pratt algorithm. I suppose you are implicitly assuming that your pattern is present in the list just one time, or you are just interested in knowing if it's in or not.

If you want the list of each first element which starts the sequence, then you can use KMP. Think about it as a sort of string.find() for lists.

I hope this will help.

answered Jan 24 '13 at 09:04

user_1177868

414
4
18

very useful @filannim. Thanks – Andy K Jul 19 '16 at 09:32

score 1 · Answer 3 · edited Jul 19 '16 at 09:36

l = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 2, 1, 1, 2, 0, 0, 0, 0],
[0, 0, 2, 1, 1, 2, 2, 0, 0, 1],
[0, 0, 1, 2, 2, 0, 1, 0, 0, 2],
[1, 0, 1, 1, 1, 2, 1, 0, 2, 1]]
import re
for i in l:
    if re.search('2, 1, 1, 2' , str(i).strip('[').strip(']')): 
        print " pattern found"

str(list) will return the string with spaces between the elements... You should look for '2, 1, 1, 2' instead of 2,1,1,2

score 0 · Answer 4 · answered Oct 02 '11 at 17:15

Here is the same idea, without regex

data = [
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
     [0, 0, 2, 1, 1, 2, 0, 0, 0, 0],
     [0, 0, 2, 1, 1, 2, 2, 0, 0, 1],
     [0, 0, 1, 2, 2, 0, 1, 0, 0, 2],
     [1, 0, 1, 1, 1, 2, 1, 0, 2, 1],
]

pattern = '2112'

for item in data:
    line = ''
    for number in item:
        line += str(number)
    if pattern in line:
        print 'pattern found: %s' % item

Because strings are immutable, appending using += in this way is slow. It's better to accumulate the elements of the string in a list and join them at the end - ie replace the inner for loop with this: line = ''.join([str(i) for i in item]) — joshayers, Oct 02 '11 at 21:42

Find sub list inside a list in python

4 Answers4

Linked