testing if a list contains a sublist

John Posner jjposner at codicesoftware.com
Tue Aug 16 15:57:37 CEST 2011


On 2:59 PM, Nobody wrote:
> On Tue, 16 Aug 2011 01:26:54 +0200, Johannes wrote:
>
>> what is the best way to check if a given list (lets call it l1) is
>> totally contained in a second list (l2)?
> "Best" is subjective. AFAIK, the theoretically-optimal algorithm is
> Boyer-Moore. But that would require a fair amount of code, and Python
> isn't a particularly fast language, so you're likely to get better results
> if you can delegate most of the leg-work to a native library (along the
> lines of Roy's suggestion of using regexps).
>
>
How about using Python's core support for "==" on list objects:

def contains(alist, slist):
    """
    predicate: is *slist* a sublist of *alist*?
    """
    alist_sz = len(alist)
    slist_sz = len(slist)
   
    # special cases
    if slist_sz == 0:       
        return True # empty list *is* a sublist
    elif slist_sz == alist_sz and alist == slist:
        return True
    elif slist_sz > alist_sz:
        return False

    # standard case
    for i in range(alist_sz - slist_sz + 1):
        if slist == alist[i:i+slist_sz]:
            return True
    # fell through "for" loop: no match found
    return False

-John




More information about the Python-list mailing list