Python: Find A List Within Members Of Another List(in Order)

February 28, 2024 Post a Comment

If I have this: a='abcdefghij' b='de' Then this finds b in a: b in a => True Is there a way of doing an similar thing with lists? Like this: a=list('abcdefghij') b=list('de')

Solution 1:

I suspect there are more pythonic ways of doing it, but at least it gets the job done:

l=list('abcdefgh')
pat=list('de')

print pat in l # Returns Falseprintany(l[i:i+len(pat)]==pat for i in xrange(len(l)-len(pat)+1))

Solution 2:

Don't know if this is very pythonic, but I would do it in this way:

defis_sublist(a, b):
    ifnot a: returnTrueifnot b: returnFalsereturn b[:len(a)] == a or is_sublist(a, b[1:])

Shorter solution is offered in this discussion, but it suffers from the same problems as solutions with set - it doesn't consider order of elements.

UPDATE: Inspired by MAK I introduced more concise and clear version of my code.

UPDATE: There are performance concerns about this method, due to list copying in slices. Also, as it is recursive, you can encounter recursion limit for long lists. To eliminate copying, you can use Numpy slices which creates views, not copies. If you encounter performance or recursion limit issues you should use solution without recursion.

Solution 3:

I think this will be faster - It uses C implementation list.index to search for the first element, and goes from there on.

def find_sublist(sub, bigger):
    if not bigger:
        return -1if not sub:
        return0
    first, rest = sub[0], sub[1:]
    pos = 0try:
        while True:
            pos = bigger.index(first, pos) + 1if not rest or bigger[pos:pos+len(rest)] == rest:
                return pos
    except ValueError:
        return -1data = list('abcdfghdesdkflksdkeeddefaksda')
print find_sublist(list('def'), data)

Note that this returns the position of the sublist in the list, not just True or False. If you want just a bool you could use this:

def is_sublist(sub, bigger): 
    return find_sublist(sub, bigger) >= 0

Solution 4:

I timed the accepted solution, my earlier solution and a new one with an index. The one with the index is clearly best.

EDIT: I timed nosklo's solution, it's even much better than what I came up with. :)

defis_sublist_index(a, b):
    ifnot a:
        returnTrue

    index = 0for elem in b:
        if elem == a[index]:
            index += 1if index == len(a):
                returnTrueelif elem == a[0]:
            index = 1else:
            index = 0returnFalsedefis_sublist(a, b):
    returnstr(a)[1:-1] instr(b)[1:-1]

defis_sublist_copylist(a, b):
    if a == []: returnTrueif b == []: returnFalsereturn b[:len(a)] == a or is_sublist_copylist(a, b[1:])

from timeit import Timer
print Timer('is_sublist([99999], range(100000))', setup='from __main__ import is_sublist').timeit(number=100)
print Timer('is_sublist_copylist([99999], range(100000))', setup='from __main__ import is_sublist_copylist').timeit(number=100)
print Timer('is_sublist_index([99999], range(100000))', setup='from __main__ import is_sublist_index').timeit(number=100)
print Timer('sublist_nosklo([99999], range(100000))', setup='from __main__ import sublist_nosklo').timeit(number=100)

Output in seconds:

4.51677298546

4.5824368

1.87861895561

0.357429027557

Solution 5:

So, if you aren't concerned about the order the subset appears, you can do:

a=list('abcdefghij')
b=list('de')
set(b).issubset(set(a))

True

Edit after you clarify: If you need to preserve order, and the list is indeed characters as in your question, you can use:

''.join(a).find(''.join(b)) > 0

Python Playground