Re: testing if a list contains a sublist

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<gandalf@shopzeus.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.026
X-Spam-Evidence	'H': 0.95; 'S': 0.00; 'example:': 0.03; 'way:': 0.05; 'not?': 0.09; 'ignores': 0.16; 'requirement:': 0.16; 'sublist': 0.16; 'meant': 0.17; 'subject:list': 0.18; 'header:In- Reply-To:1': 0.22; 'interpreted': 0.23; 'skip:[ 10': 0.27; 'lists': 0.28; 'elements': 0.29; 'not.': 0.30; 'relation': 0.30; 'error': 0.32; 'list': 0.32; 'words,': 0.32; 'does': 0.32; 'to:addr:python-list': 0.33; 'however,': 0.34; 'header:User- Agent:1': 0.34; 'right,': 0.34; 'clarify': 0.34; 'lists?': 0.34; 'post': 0.36; 'skip:" 10': 0.36; 'but': 0.37; 'two': 0.37; 'easier': 0.38; 'subject:: ': 0.39; 'received:192': 0.39; 'to:addr:python.org': 0.39; 'order': 0.62; 'stated': 0.67; 'order,': 0.73; 'free?': 0.84
Date	Tue, 16 Aug 2011 10:00:15 +0200
From	Laszlo Nagy <gandalf@shopzeus.com>
User-Agent	Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.18) Gecko/20110617 Thunderbird/3.1.11
MIME-Version	1.0
To	python-list@python.org
Subject	Re: testing if a list contains a sublist
References	<mailman.27.1313450819.27778.python-list@python.org> <roy-77629E.20531315082011@news.panix.com> <mailman.37.1313477497.27778.python-list@python.org> <3bb01409-ee5e-4494-bef8-93029dd49ecb@h9g2000vbr.googlegroups.com>
In-Reply-To	<3bb01409-ee5e-4494-bef8-93029dd49ecb@h9g2000vbr.googlegroups.com>
Content-Type	text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding	7bit
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.45.1313481619.27778.python-list@python.org> (permalink)
Lines	35
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1313481619 news.xs4all.nl 23894 [2001:888:2000:d::a6]:54954
X-Complaints-To	abuse@xs4all.nl
Xref	x330-a1.tempe.blueboxinc.net comp.lang.python:11524

Show key headers only | View raw

> Error free? Consider this stated requirement:
>> l1 = [1,2,2,], l2 = [1,2,3,4,5] ->  l1 is not contained in l2
If you look it the strict way, "containment" relation for lists is meant 
this way:


l1 = []
l2 = [1,l1,2]   # l2 CONTAINS l1

But you are right, I was wrong. So let's clarify what the OP wants!

For example:

l1 = [1,2,2,], l2 = [2,1,2,3,4,5]


What is the relation between these two lists? Does l2 contain l1 or not? 
In other words, is this "containment" relation interpreted on multisets 
not considering the order of the items?

>
> It also completely ignores list order, which would make [9,8,7] a
> sublist of [5,6,7,8,9].
Exactly. However, from the original post of Johannes it was not clear if 
the order of the elements counts or not.

If It this is interpreted as a multiset relation, it would be easier to 
use collections.Counter. If the order of elements is important then he 
can start with a Boyer-Moore algorithm.

Best,

   Laszlo

Thread

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

csiph-web