Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #11480 > unrolled thread

testing if a list contains a sublist

Back to article view | Back to comp.lang.python

Contents

  testing if a list contains a sublist Johannes <dajo.mail@web.de> - 2011-08-16 01:26 +0200
    Re: testing if a list contains a sublist Roy Smith <roy@panix.com> - 2011-08-15 20:53 -0400
      Re: testing if a list contains a sublist Laszlo Nagy <gandalf@shopzeus.com> - 2011-08-16 08:51 +0200
        Re: testing if a list contains a sublist alex23 <wuwei23@gmail.com> - 2011-08-16 00:19 -0700
        Re: testing if a list contains a sublist alex23 <wuwei23@gmail.com> - 2011-08-16 00:14 -0700
          Re: testing if a list contains a sublist Laszlo Nagy <gandalf@shopzeus.com> - 2011-08-16 10:00 +0200
          Re: testing if a list contains a sublist Johannes <dajo.mail@web.de> - 2011-08-16 17:26 +0200
        Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-16 00:24 -0700
      Re: testing if a list contains a sublist Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2011-08-16 14:23 +0200
        Re: testing if a list contains a sublist Roy Smith <roy@panix.com> - 2011-08-16 08:53 -0400
        Re: testing if a list contains a sublist nn <pruebauno@latinmail.com> - 2011-08-16 07:53 -0700
          Re: testing if a list contains a sublist Laszlo Nagy <gandalf@shopzeus.com> - 2011-08-16 17:17 +0200
            Re: testing if a list contains a sublist Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2011-08-16 17:39 +0200
          Re: testing if a list contains a sublist Neil Cerutti <neilc@norwich.edu> - 2011-08-16 17:45 +0000
    Re: testing if a list contains a sublist Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-08-16 12:12 +1000
      Re: testing if a list contains a sublist Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-08-16 18:19 +1000
    Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-15 23:14 -0700
    Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-15 23:13 -0700
    Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-15 23:14 -0700
      Re: testing if a list contains a sublist Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-08-16 18:37 +1000
        Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-16 21:13 -0700
    Re: testing if a list contains a sublist Nobody <nobody@nowhere.com> - 2011-08-16 12:21 +0100
      Re: testing if a list contains a sublist John Posner <jjposner@codicesoftware.com> - 2011-08-16 09:57 -0400
      Re: testing if a list contains a sublist John Posner <jjposner@optimum.net> - 2011-08-16 09:57 -0400
        Re: testing if a list contains a sublist Nobody <nobody@nowhere.com> - 2011-08-17 13:28 +0100
    Re: testing if a list contains a sublist Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-08-20 12:10 +1000

Page 2 of 2 — ← Prev page 1 [2]

#11655

On Aug 16, 1:37 am, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:
> On Tue, 16 Aug 2011 04:14 pm ChasBrown wrote:
>
>
>
> > On Aug 15, 4:26 pm, Johannes <dajo.m...@web.de> wrote:
> >> hi list,
> >> what is the best way to check if a given list (lets call it l1) is
> >> totally contained in a second list (l2)?
>
> >> for example:
> >> l1 = [1,2], l2 = [1,2,3,4,5] -> l1 is contained in l2
> >> l1 = [1,2,2,], l2 = [1,2,3,4,5] -> l1 is not contained in l2
> >> l1 = [1,2,3], l2 = [1,3,5,7] -> l1 is not contained in l2
>
> >> my problem is the second example, which makes it impossible to work with
> >> sets insteads of lists. But something like set.issubset for lists would
> >> be nice.
>
> >> greatz Johannes
>
> > My best guess:
>
> > from collections import Counter
>
> There's no reason to think that the Original Poster wants a multiset based
> solution. He asked about lists and sublists. That's a standard term, like
> substring:
>
> "12" is a substring of "01234".
> "21" and "13" are not.
>
> [1, 2] is a sublist of [0, 1, 2, 3, 4].
> [2, 1] and [1, 3] are not.
>
> Since lists are ordered, so are sublists.
>

That's reasonable; although except in the subject, the OP never uses
the term 'sublist'; instead using more ambiguous terms like
'contains', 'is totally contained', etc., with definition by limited
example. So it was a bit of a guess on my part of what was wanted.

> If the OP does want a solution that ignores order, then he needs to describe
> his problem better.

As it turns out, in another response the OP says he wants [2,1,2] to
be 'contained' by [1,2,2]. But in any case he always has sorted lists,
in which case, interestingly, the multiset approach and your more
canonical sublist approach yield the same results.

Cheers - Chas

[toc] | [prev] | [next] | [standalone]

#11541

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).

[toc] | [prev] | [next] | [standalone]

#11556

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

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#11679

On Tue, 16 Aug 2011 09:57:57 -0400, John Posner wrote:

> How about using Python's core support for "==" on list objects:

>     for i in range(alist_sz - slist_sz + 1):
>         if slist == alist[i:i+slist_sz]:
>             return True

This is bound to be asymptotically O(alist_sz * slist_sz), even if the
constant factor is reduced by use of ==. Boyer-Moore and regexps are
asymptotically O(alist_sz). However, the setup costs are much higher, so
you might need alist_sz to be very large before they win out.

[toc] | [prev] | [next] | [standalone]

#11894

Johannes wrote:

> hi list,
> what is the best way to check if a given list (lets call it l1) is
> totally contained in a second list (l2)?
[...]

For anyone interested, here's a pair of functions that implement
sub-sequence testing similar to str.find and str.rfind:


http://code.activestate.com/recipes/577850-search-sequences-for-sub-sequence/



-- 
Steven

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.python

csiph-web