Seeing if a list exists within another list?

Question

Basically lets say i have:

>>> a = [1,3,2,2,2]
>>> b = [1,3,2]

I want to see if the all the elements in b, exists within a, and in the same order. So for the above example b would exist within a.

I am kinda hoping theres a really simple one line answer.

Answer 1

This is a simple O(n * m) algorithm:

any(a[i:i + len(b)] == b for i in range(len(a) - len(b) + 1))

Note that is not the fastest way of doing this. If you need high performance you could use similar techniques to those used in string searching algorithms.

Answer 2

This is probably not very efficient, but you could use:

In [1]: a = [1,3,2,2,2]

In [2]: b = [1,3,2]

In [3]: b == [val for val in a if val in b]
Out[3]: False

In [4]: a = [6,1,3,2,5,4]

In [5]: b == [val for val in a if val in b]
Out[5]: True

The first test returns False because of the duplicates of 2. The question is how you want to deal with duplicates in general. If you only want to cut them off at the end then you could trim the list to the length of a:

In [6]: a = [1,3,2,2,2]

In [7]: b == [val for val in a if val in b][:len(b)]
Out[7]: True

Answer 3

if its "in the same order",

>>> a = [1,3,2,2,2]
>>> b = [1,3,2]
>>> ' '.join(map(str,b)) in ' '.join(map(str,a))
True

>>> a = [1,1,2,2,2,13,2]
>>> b = [1,3,2]
>>> ' '.join(map(str,b)) in ' '.join(map(str,a))
False

Answer 4

Here's a solution that works for lists of ints.

Turn for example [1, 3, 2] into the string "'1', '3', '2'". Then use built-in string inclusion to see if it's in the other list.

repr(map(str, b))[1:-1] in repr(map(str, a))[1:-1]

Answer 5

If by 'in the same order' you meant subsequence (as opposed to substring) then this non-one-liner should work fast:

  def is_subsequence(x, y):
    i, j = 0, 0
    while i < len(x) and j < len(y):
      if x[i] == y[j]:
        i += 1
      j += 1
    return i == len(x)

Answer 6

Sorry, but what you want to do is effectively the same as string matching (albeit with lists instead of strings). You might want to look at Knuth-Morris-Pratt or Boyer Moore for a linear time algorithm.

EDIT:
I am assuming that by "in order" you mean consecutively anywhere in the sequence. If they can be separated by other elements in between, then this is not the solution you want.