# How to test if a list contains another list?

Posted on

### Question :

How to test if a list contains another list?

How can I test if a list contains another list (ie. it’s a contiguous subsequence). Say there was a function called contains:

``````contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end])
contains([1,3], [-1, 0, 1, 2]) # Returns False
contains([1, 2], [[1, 2], 3]) # Returns False
contains([[1, 2]], [[1, 2], 3]) # Returns [0, 0]
``````

Edit:

``````contains([2, 1], [-1, 0, 1, 2]) # Returns False
contains([-1, 1, 2], [-1, 0, 1, 2]) # Returns False
contains([0, 1, 2], [-1, 0, 1, 2]) # Returns [1, 3]
``````

Here is my version:

``````def contains(small, big):
for i in xrange(len(big)-len(small)+1):
for j in xrange(len(small)):
if big[i+j] != small[j]:
break
else:
return i, i+len(small)
return False
``````

It returns a tuple of (start, end+1) since I think that is more pythonic, as Andrew Jaffe points out in his comment. It does not slice any sublists so should be reasonably efficient.

One point of interest for newbies is that it uses the else clause on the for statement – this is not something I use very often but can be invaluable in situations like this.

This is identical to finding substrings in a string, so for large lists it may be more efficient to implement something like the Boyer-Moore algorithm.

If all items are unique, you can use sets.

``````>>> items = set([-1, 0, 1, 2])
>>> set([1, 2]).issubset(items)
True
>>> set([1, 3]).issubset(items)
False
``````

There’s an `all()` and `any()` function to do this.
To check if `big` contains ALL elements in `small`

``````result = all(elem in big for elem in small)
``````

To check if `small` contains ANY elements in `big`

``````result = any(elem in big for elem in small)
``````

the variable result would be boolean (TRUE/FALSE).

May I humbly suggest the Rabin-Karp algorithm if the `big` list is really big. The link even contains almost-usable code in almost-Python.

This works and is fairly fast since it does the linear searching using the builtin `list.index()` method and `==` operator:

``````def contains(sub, pri):
M, N = len(pri), len(sub)
i, LAST = 0, M-N+1
while True:
try:
found = pri.index(sub, i, LAST) # find first elem in sub
except ValueError:
return False
if pri[found:found+N] == sub:
return [found, found+N-1]
else:
i = found+1
``````

After OP’s edit:

``````def contains(small, big):
for i in xrange(1 + len(big) - len(small)):
if small == big[i:i+len(small)]:
return i, i + len(small) - 1
return False
``````

Here’s a straightforward algorithm that uses list methods:

``````#!/usr/bin/env python

def list_find(what, where):
"""Find `what` list in the `where` list.

Return index in `where` where `what` starts
or -1 if no such index.

>>> f = list_find
>>> f([2, 1], [-1, 0, 1, 2])
-1
>>> f([-1, 1, 2], [-1, 0, 1, 2])
-1
>>> f([0, 1, 2], [-1, 0, 1, 2])
1
>>> f([1,2], [-1, 0, 1, 2])
2
>>> f([1,3], [-1, 0, 1, 2])
-1
>>> f([1, 2], [[1, 2], 3])
-1
>>> f([[1, 2]], [[1, 2], 3])
0
"""
if not what: # empty list is always found
return 0
try:
index = 0
while True:
index = where.index(what, index)
if where[index:index+len(what)] == what:
return index # found
index += 1 # try next position
except ValueError:

def contains(what, where):
"""Return [start, end+1] if found else empty list."""
i = list_find(what, where)
return [i, i + len(what)] if i >= 0 else [] #NOTE: bool([]) == False

if __name__=="__main__":
import doctest; doctest.testmod()
``````

``````def contains(subseq, inseq):