Determine if all elements in a list are present and in the same order in another list

Question

How do I create a function sublist() that takes two lists, list1 and list2, and returns True if list1 is a sublist of list2, and False otherwise. list1 is a sublist of list2 if the numbers in list1 appear in list2 in the same order as they appear in list1, but not necessarily consecutively. For example,

>>> sublist([1, 12, 3],[25, 1, 30, 12, 3, 40])
True

>>> sublist([5, 90, 2],[90, 20, 5, 2, 17])
False

Answer 1

Here's one way to do it in linear time (and constant space) with an iterator:

def sublist(a, b):
    seq = iter(b)
    try:
        for x in a:
            while next(seq) != x: pass
        else:
            return True
    except StopIteration:
        pass
    return False

Basically it goes through each element of the sublist, and sees if it can find that same element in the part of the complete list it hasn't looked at yet. If it makes it through the entire sublist it means we have a match (hence the else statement on the for loop). If we run out of elements to look at in the complete list, it means we don't have a match.

Edit: I have updated my solution so it works with Python 3. For Python 2.5 and older, next(seq) needs to be replaced with seq.next().

Answer 2

A very rough solution:

def sublist(a, b):
    if not a:
        return True
    for k in range(len(b)):
        if a[0] == b[k]:
            return sublist(a[1:], b[k+1:])
    return False

print sublist([1, 12, 3], [25, 1, 30, 12, 3, 40]) # True
print sublist([12, 1, 3], [25, 1, 30, 12, 3, 40]) # False

Edit: Speed upgrade

Answer 3

Here's an iterative solution which should have optimal asymptotics:

def sublist(x, y):
    if x and not y:
        return False
    i, lim = 0, len(y)
    for e in x:
        while e != y[i]:
            i += 1
            if i == lim:
                return False
        i += 1
    return True

@sshashank124's solution has the same complexity, but the dynamics will be somewhat different: his version traverses the second argument multiple times, but because it pushes more work into the C layer it'll probably be much faster on smaller input.

Edit: @hetman's solution has essentially the same logic, but is much more Pythonic, although, contrary to my expectation, it seems to be slightly slower. (I was also incorrect about the performance of @sshashan124's solution; the overhead of the recursive calls appears to outweigh the benefit of doing more work in C.)