Is there a way to know if a list of elements is on a larger list without using 'in' keyword?

Question

I want to do this. I have two python lists, one larger than the other and I want to know is there is a way to check if the elements of the smaller list are in the big list in the exact same order for example:

small_list = [4,2,5]
big_list = [1,2,5,7,2,4,2,5,67,8,5,13,45]

I tried using the in keyword but It did not worked :'(

Answer 1

There's no built in operator doing that particular comparison. I suggest a list comprehension or a quick for loop.

Answer 2

Rather non-optimized, demonstrates the general strategy simply:

tuple(small_list) in zip(big_list[:], big_list[1:], big_list[2:])

The funky zip thing does this:

>>> zip(big_list[:], big_list[1:], big_list[2:])
[(1, 2, 5), (2, 5, 7), (5, 7, 2), (7, 2, 4), (2, 4, 2), (4, 2, 5), (2, 5, 67), (5, 67, 8), (67, 8, 5), (8, 5, 13), (5, 13, 45)]

A more optimized version:

from itertools import izip, islice
tuple(small_list) in izip(big_list, islice(big_list, 1, None), islice(big_list, 2, None))

To handle small_list length of any size:

from itertools import izip, islice
tuple(small_list) in izip(*(islice(big_list, i, None) for i in xrange(len(small_list))))

Answer 3

This problem is trickier than it seems. Unless I'm mistaken, it's a special case of the longest common substring problem.

For the general case (arbitrarily large lists), I would use some kind of finite state automaton, akin to a regular expression. I believe the result could then be calculated in O(mn) time.

Answer 4

That's because small_list in big_list checks whether an element in big_list is equal to small_list. What you want to do instead is see if a slice of big_list is the same as small_list.

def isSubList(slice, L):
    n = len(slice)
    for i in range(0, len(L) - n):
        if slice == L[i:i+n]:
            return True
    return False

isSubList(small_list, big_list)

Answer 5

def in_list(small, big):
    l_sml = len(small)
    l_big = len(big)
    return any((big[i:i+l_sml]==small for i in xrange(l_big-l_sml+1)))

print in_list([4,2,1], [1,2,3,4,2,1,0,5]) # True
print in_list([1,2,3], [1,2,4])           # False

Answer 6

Edit: Leaving the answer here but I failed to note the requirement that they be in the same order. This does not meet that requirement

Quick and dirty answer. Based it off of the answer for Python - Intersection of two lists

small_list == filter( lambda x: x in big_list, small_list)

Answer 7

you could use sets

from sets import Set
small_set = set(small_list)
big_set = set(big_list)
small_set <= big_set

<= is the subset operator

Answer 8

Hmm, maybe it's overkill, but you can use the SequenceMatcher class from difflib:

from difflib import SequenceMatcher 
small_list = [4,2,5]
big_list = [1,2,5,7,2,4,2,5,67,8,5,13,45]
print SequenceMatcher(None, small_list, big_list).get_matching_blocks()

difflib documentation

Answer 9

If you know a reasonable bound of your numbers, you can convert them to a Python type whose 'in' operator does this automatically. The two I know are str and unicode.

Then you ask the strings if the smaller is in the larger, this does a substring comparison:

>>> small_list = [4,2,5]
>>> big_list = [1,2,5,7,2,4,2,5,67,8,5,13,45]
>>>
>>> def encode(lst):
      return u"".join(unichr(c) for c in lst)

>>> encode(small_list) in encode(big_list)
True

(You can "encode" to str if all numbers are in 0 <= x <= 255, you can "encode" to unicode if all are in 0 <= x <= sys.maxunicode ).

Answer 10

If you want to use the "in" keyword to do what you want, you can override contains using one of the solutions mentioned in the answers here:

class mylist(list):
    def __contains__(self, lst):
        return ':'.join(map(str, lst)) in ':'.join(map(str, self))

small_list = mylist([4,2,5])
big_list = mylist([1,2,5,7,2,4,2,5,67,8,5,13,45])

print small_list in big_list

Edit: Addresses Jeffrey's comment.