3

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.

UberJumper
  • 20,245
  • 19
  • 69
  • 87
  • 2
    What have you tried so far? This sounds like homework, so it would be good to show what you've done. – S.Lott Feb 21 '10 at 11:46
  • 4
    Do you mean: "I want to see if the all the elements in b exist **consecutively** within a". "In the same order" is a weaker statement. – Mark Byers Feb 21 '10 at 12:02
  • Sorry i tried doing it the long way of simply going through a, checking if the first element is right, then continuing on, if the next is equal to second continue, else start over. Writing this big loop just seems tedious and sloppy. However i am going to be using this alot. This is for a work project related to run length encoding used by a certain ordering system/delivery. Basically the only way we can really interact and have custom functionality is to work directly with the work order, which is a terrible 80's code cthulu. – UberJumper Feb 21 '10 at 13:14
  • So do they have to be consecutive ('substring') or not ('subsequence')? –  Feb 21 '10 at 15:20
  • Related: http://stackoverflow.com/questions/425604/best-way-to-determine-if-a-sequence-is-in-another-sequence-in-python http://stackoverflow.com/questions/483429/how-to-find-similar-patterns-in-lists-arrays-of-strings – jfs Feb 21 '10 at 21:03

6 Answers6

6

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.

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
2

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)
  • If you intend your code to be self-commenting, you really should rename `x` and `y` into more descriptive names; otherwise, document your code and explain which is which. Is it `is_subsequence("abcecde", "cde")` or `is_subsequence("cde", "abcecde")`? – tzot Feb 22 '10 at 22:27
1

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]
0

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
nikow
  • 21,190
  • 7
  • 49
  • 70
0

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.

Michael Aaron Safyan
  • 93,612
  • 16
  • 138
  • 200
-2

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
ghostdog74
  • 327,991
  • 56
  • 259
  • 343
  • This also returns `True` for `b = [13, 2]`. (There's no requirement for the string representation of the elements in the lists to all be one character long). – Scott Griffiths Feb 21 '10 at 12:58
  • then we join with a space and not will null. that should fix it. – ghostdog74 Feb 21 '10 at 15:13
  • Sorry, that doesn't fix it. This would now return `True` for `a = ['1', '2']` and `b = ['1 2']`. (There's also no requirement in the question for the elements to be numbers). – Scott Griffiths Feb 21 '10 at 17:03
  • there is also no requirement for elements not to be numbers. – ghostdog74 Feb 22 '10 at 00:04
  • 1
    The requirement is just that they are lists, and your method doesn't work for many cases. If you add a proviso in your answer that it only works for numbers then that's fine. Otherwise you could argue that there's no requirement for them to be anything other than the explicitly stated numbers, in which case the best answer is just `True`. – Scott Griffiths Feb 22 '10 at 08:48