Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <jjposner@optimum.net>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.000
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'elif': 0.04; '"""': 0.07; 'python': 0.08; '*is*': 0.09; 'header:In-reply-to:1': 0.09; 'algorithm': 0.13; 'def': 0.15; 'library': 0.15; '"=="': 0.16; '"for"': 0.16; '-john': 0.16; 'alist': 0.16; 'objects:': 0.16; 'received:167.206.4': 0.16; 'received:167.206.4.200': 0.16; 'received:cv.net': 0.16; 'received:hcvlny.cv.net': 0.16; 'received:mta5.srv.hcvlny.cv.net': 0.16; 'received:srv.hcvlny.cv.net': 0.16; 'sublist': 0.16; 'wrote:': 0.16; 'language,': 0.17; 'subject:list': 0.18; 'to:name:python- list': 0.18; 'tue,': 0.23; 'pm,': 0.24; 'aug': 0.24; "python's": 0.24; 'suggestion': 0.26; 'code,': 0.28; 'second': 0.29; 'lines': 0.30; 'match': 0.30; '+0200,': 0.30; 'list': 0.32; 'cases': 0.32; "isn't": 0.33; 'to:addr:python-list': 0.33; 'header:User-Agent:1': 0.34; 'nobody': 0.34; 'totally': 0.35; 'core': 0.36; 'fair': 0.37; 'using': 0.37; 'but': 0.37; 'subject:: ': 0.39; 'received:192': 0.39; 'empty': 0.39; 'to:addr:python.org': 0.39; 'case': 0.39; 'results': 0.61; 'special': 0.67
Date: Tue, 16 Aug 2011 09:57:57 -0400
From: John Posner <jjposner@optimum.net>
Subject: Re: testing if a list contains a sublist
In-reply-to: <pan.2011.08.16.11.21.47.168000@nowhere.com>
To: python-list <python-list@python.org>
MIME-version: 1.0
Content-type: text/plain; charset=ISO-8859-1
Content-transfer-encoding: 7BIT
X-Enigmail-Version: 1.2
References: <mailman.27.1313450819.27778.python-list@python.org> <pan.2011.08.16.11.21.47.168000@nowhere.com>
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:5.0) Gecko/20110624 Thunderbird/5.0
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.65.1313504884.27778.python-list@python.org>
Lines: 38
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1313504884 news.xs4all.nl 23874 [2001:888:2000:d::a6]:53105
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:11557

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