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 1 of 2  [1] 2  Next page →

#11480 — testing if a list contains a sublist

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

[toc] | [next] | [standalone]

#11490

In article <mailman.27.1313450819.27778.python-list@python.org>,
 Johannes <dajo.mail@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

import re

def sublist(l1, l2):
    s1 = ''.join(map(str, l1))
    s2 = ''.join(map(str, l2))
    return re.search(s1, s2)

assert sublist([1,2], [1,2,3,4,5])
assert not sublist ([1,2,2], [1,2,3,4,5])
assert not sublist([1,2,3], [1,3,5,7])


(running and ducking)

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

#11513

>> 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
Fastest, error-free and simplest solution is to use sets:

 >>> l1 = [1,2]
 >>> l2 = [1,2,3,4,5]
 >>> set(l1)-set(l2)
set([])
 >>> set(l2)-set(l1)
set([3, 4, 5])
 >>>

Although with big lists, this is not very memory efficient. But I must 
tell you, sometimes I use this method for lists with millions of 
integers, and it is very fast and reliable, and memory is not a concern 
for me, at least - some million integers will fit into a few MB of 
memory. Read the docs about set operators  for creating union, symmetric 
difference etc.

Best,

    Laszlo

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

#11517

Laszlo Nagy <gand...@shopzeus.com> wrote:
> Fastest, error-free and simplest solution is to use sets:
>
>  >>> l1 = [1,2]
>  >>> l2 = [1,2,3,4,5]
>  >>> set(l1)-set(l2)
> set([])
>  >>> set(l2)-set(l1)
> set([3, 4, 5])
>  >>>

Error-free? Not given the stated requirements:

> l1 = [1,2,2,], l2 = [1,2,3,4,5] -> l1 is not contained in l2

>>> l1 = [1,2,2]
>>> l2 = [1,2,3,4,5]
>>> set(l1)-set(l2)
set()
>>> set(l2)-set(l1)
{3, 4, 5}

As you can see, using sets provides the exact same result for a non-
contained sub-list as it does for your valid example. The list
[1,2,2,2,2,2,2,2,2] is clearly not contained with [1,2,3], but your
code would say it is.

Similarly, [9,8,7] would appear to be a sub-list of [5,6,7,8,9],
something I'd also considered to be false in this instance.

(My apologies if this is a double-up, the original post hasn't
appeared yet)

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

#11518

On Aug 16, 4:51 pm, Laszlo Nagy <gand...@shopzeus.com> 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
>
> Fastest, error-free and simplest solution is to use sets:
>
>  >>> l1 = [1,2]
>  >>> l2 = [1,2,3,4,5]
>  >>> set(l1)-set(l2)
> set([])
>  >>> set(l2)-set(l1)
> set([3, 4, 5])

Error free? Consider this stated requirement:
> l1 = [1,2,2,], l2 = [1,2,3,4,5] -> l1 is not contained in l2

>>> l1 = [1,2,2]
>>> l2 = [1,2,3,4,5]
>>> set(l1)-set(l2)
set()
>>> set(l2)-set(l1)
{3, 4, 5}

So set([1,2]) == set([1,2,2]), despite [1,2,2] not being a sublist of
the original.

It also completely ignores list order, which would make [9,8,7] a
sublist of [5,6,7,8,9].

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

#11524

> 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

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

#11565

Am 16.08.2011 10:00, schrieb Laszlo Nagy:
> 
>> 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]
I dont care about this case, because all list are ordered for me.

I've chosen the following solution

> def _list_contained_in_list(l1,l2):
>     d1 = {}
>     d2 = {}
>     for i in l1:
>         if i in d1:
>             d1[i] += 1
>         else:
>             d1[i] = 1
>     for i in l2:
>         if i in d2:
>             d2[i] += 1
>         else:
>             d2[i] = 1
>     if not all([k in d2.keys() for k in d1.keys()]):
>         return false    
>     return all([d1[i] <= d2[i] for i in d1])


greatz Johannes

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

#11521

On Aug 15, 11:51 pm, Laszlo Nagy <gand...@shopzeus.com> 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
>
> Fastest, error-free and simplest solution is to use sets:
>
>  >>> l1 = [1,2]
>  >>> l2 = [1,2,3,4,5]
>  >>> set(l1)-set(l2)
> set([])
>  >>> set(l2)-set(l1)
> set([3, 4, 5])
>  >>>
>

This approach fails the OP's desires when

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

The OP explicitly desires 'l2 contains l1' to be false in that case.

Cheers - Chas

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

#11546

Roy Smith <roy@panix.com> writes:

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

[...]
> import re
>
> def sublist(l1, l2):
>     s1 = ''.join(map(str, l1))
>     s2 = ''.join(map(str, l2))
>     return re.search(s1, s2)

This is complete nonsense (try it on [12] and [1,2]).

The original problem is "string searching" (where strings here are
sequences of numbers instead of characters). See

http://en.wikipedia.org/wiki/String_searching_algorithm

for any algorithm (Rabin-Karp seems appropriate to me).

-- Alain.

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

#11549

In article <8739h18rzj.fsf@dpt-info.u-strasbg.fr>,
 Alain Ketterlin <alain@dpt-info.u-strasbg.fr> wrote:

> Roy Smith <roy@panix.com> writes:
> 
> >> what is the best way to check if a given list (lets call it l1) is
> >> totally contained in a second list (l2)?
> 
> [...]
> > import re
> >
> > def sublist(l1, l2):
> >     s1 = ''.join(map(str, l1))
> >     s2 = ''.join(map(str, l2))
> >     return re.search(s1, s2)
> 
> This is complete nonsense (try it on [12] and [1,2]).

No, it's not complete nonsense, it works just fine for the limited data 
set the OP presented :-)  Of course, you are correct that it only works 
for single-digit integers, hence my "running and ducking" comment.

> The original problem is "string searching" (where strings here are
> sequences of numbers instead of characters). See
> 
> http://en.wikipedia.org/wiki/String_searching_algorithm
> 
> for any algorithm (Rabin-Karp seems appropriate to me).

Yes, of course this is fundamentally a string searching problem.  The 
problem is that while Python comes with an excellent tool for doing 
these kinds of string searches, its domain is limited to, as you pointed 
out, character strings.  However, for the limited data the OP presented, 
there is a trivial way to map the original data domain (single digit 
integers) into the domain the re library knows about (character 
strings).  My answer may be a sucky general-purpose solution, but it's 
also a neat hack, and sometimes a neat hack is what you need.

It also occurs to me that this hack could be expanded a bit to handle a 
much larger input domain.  If you had sequences of arbitrary (but 
hashable) objects, you could map this into a unicode string where each 
"character" is the 32-bit hash of of the corresponding input object, 
then run the regex search on that.

In theory, it should work.  In practice, I can see a few potential 
problems:

1) You might have to carefully craft your hash function to avoid magic 
unicode values like null or BOM.  No biggie there.

2) Hash collisions can lead to false positives, so you need to filter 
those out with a subsequent linear comparison step.  Of course, this is 
true of any kind of hash lookup.  No biggie there either.

3) While the re module is advertised to work on unicode data, I have no 
idea how efficient it is on arbitrary values.  I wouldn't be too 
surprised if it's tuned for "mostly ascii utf-8" and performance suffers 
on completely random strings.  If its first step is to transcode to 
utf-32 internally, I expect it would work just fine, but it would take 
some experimentation (or reading of the source code) to validate this 
assumption.

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

#11560

On Aug 16, 8:23 am, Alain Ketterlin <al...@dpt-info.u-strasbg.fr>
wrote:
> Roy Smith <r...@panix.com> writes:
> >> what is the best way to check if a given list (lets call it l1) is
> >> totally contained in a second list (l2)?
>
> [...]
>
> > import re
>
> > def sublist(l1, l2):
> >     s1 = ''.join(map(str, l1))
> >     s2 = ''.join(map(str, l2))
> >     return re.search(s1, s2)
>
> This is complete nonsense (try it on [12] and [1,2]).
>
> The original problem is "string searching" (where strings here are
> sequences of numbers instead of characters). See
>
> http://en.wikipedia.org/wiki/String_searching_algorithm
>
> for any algorithm (Rabin-Karp seems appropriate to me).
>
> -- Alain.

That can be easily fixed:

>>> def sublist(lst1, lst2):
	s1 = ','.join(map(str, lst1))
	s2 = ','.join(map(str, lst2))
	return False if s2.find(s1)==-1 else True

>>> sublist([1,2],[1,2,3,4,5])
True
>>> sublist([1,2,2],[1,2,3,4,5])
False
>>> sublist([1,2,3],[1,3,5,7])
False
>>> sublist([12],[1,2])
False
>>>

I don't know about best, but it works for the examples given.

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

#11563

> That can be easily fixed:
>
>>>> def sublist(lst1, lst2):
> 	s1 = ','.join(map(str, lst1))
> 	s2 = ','.join(map(str, lst2))
> 	return False if s2.find(s1)==-1 else True
>
> I don't know about best, but it works for the examples given.
>
For numbers, it will always work. But what about

lst1 = [",",",,"]
lst1 = [",",",",","]

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

#11568

Laszlo Nagy <gandalf@shopzeus.com> writes:

>>>>> def sublist(lst1, lst2):
>> 	s1 = ','.join(map(str, lst1))
>> 	s2 = ','.join(map(str, lst2))
>> 	return False if s2.find(s1)==-1 else True
>>
>> I don't know about best, but it works for the examples given.
>>
> For numbers, it will always work.

I'm not even sure: if str() is locale-sensitive, it may introduce commas
in numbers (I don't know whether str() is locale-sensitive, the doc
doesn't mention anything.)

> But what about
>
> lst1 = [",",",,"]
> lst1 = [",",",",","]

Yes.

It will also fail on nested lists, for fundamental reasons which are
impossible to handle with regexps. (Tough I'm not sure the OP had nested
lists in mind.)

The "brute-force" algorithm given somewhere else in this thread is
probably the way to go, unless the lists are really long, in which case
one of the "string searching" algorithm should be used (I would be
surprised noone has implemented Boyer-Moore or Karp-Rabin).

-- Alain.

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

#11590

On 2011-08-16, nn <pruebauno@latinmail.com> wrote:
> That can be easily fixed:
>
>>>> def sublist(lst1, lst2):
> 	s1 = ','.join(map(str, lst1))
> 	s2 = ','.join(map(str, lst2))
> 	return False if s2.find(s1)==-1 else True
>
>>>> sublist([1,2,3],[1,2,3,4,5])
> True
>>>> sublist([1,2,2],[1,2,3,4,5])
> False
>>>> sublist([1,2,3],[1,3,5,7])
> False
>>>> sublist([12],[1,2])
> False
>>>>

String conversion is risky:

>>> sublist(['1,2', '3,4'], [1, 2, 3, 4])
True

Since we're bike-shedding, here's my entry. It's not clear to me
if accepting iterables rather than lists is a win, but I thought,
"Why not be general if the implementation is easy?"

def is_subseq_of(x, y):
    r"""Return True if the elements in iterable x are found contiguously in
    iterable y.

    >>> is_subseq_of([], [])
    True
    >>> is_subseq_of([], [1, 2, 3])
    True
    >>> is_subseq_of([1], [1, 2, 3])
    True
    >>> is_subseq_of([1], [])
    False
    >>> is_subseq_of([4, 5], [1, 2, 3, 4, 5])
    True
    >>> is_subseq_of([1, 2], [1, 3, 2])
    False
    >>> is_subseq_of([2, 3], [1, 2, 3, 4])
    True
    >>> is_subseq_of([1, 2, 2], [1, 2, 3, 4, 5])
    False
    >>> is_subseq_of([1, 2], [1, 2])
    True
    >>> is_subseq_of([1, 2, 3], [1, 2])
    False
    >>> is_subseq_of(['1,2', '3,4'], [1, 2, 3, 4])
    False
    """
    x = tuple(x)
    ix = 0
    lenx = len(x)
    if lenx == 0:
        return True
    for elem in y:
        if x[ix] == elem:
            ix += 1
        else:
            ix = 0
        if ix == lenx:
            return True
    return False

if __name__ == '__main__':
    import doctest
    doctest.testmod()

-- 
Neil Cerutti

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

#11499

On Tue, 16 Aug 2011 09:26 am 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)?

This is not the most efficient algorithm, but for short lists it should be
plenty fast enough:


def contains(alist, sublist):
    if len(sublist) == 0 or len(sublist) > len(alist):
        return False
    start = 0
    while True:
        try:
            p = alist.index(sublist[0], start)
        except ValueError:
            return False
        for i,x in enumerate(sublist):
            if alist[p+i] != x:
                start = p+1
                break
        else:  # for loop exits without break
            return True


-- 
Steven

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

#11528

On Tue, 16 Aug 2011 12:12 pm Steven D'Aprano wrote:

> On Tue, 16 Aug 2011 09:26 am 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)?
> 
> This is not the most efficient algorithm, but for short lists it should be
> plenty fast enough:

Nope, sorry, that was buggy. Here's another version which should be accurate
but may be slower.

def search(source, target, start=0, end=None):
    """Naive search for target in source."""
    m = len(source)
    n = len(target)
    if end is None:
        end = m
    if n == 0 or m < n:
        return None
    for i in range(start, end-n+1):
        if source[i:i+n] == target:
            return i
    return None



-- 
Steven

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

#11509

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

def contains(alist, sublist):
    alist = Counter(alist)
    for k in sublist:
        try:
            alist[k] -= 1
            if alist[k] < 0:
                return False
        except KeyError:
            return False
    return True

'Counter' being better understood as 'Multiset'.

If m = len(alist) and n = len(sublist), looks to be roughly O(m+n).

Cheers - Chas

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

#11510

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

def contains(alist, sublist):
    alist = Counter(alist)
    for k in sublist:
        try:
            alist[k] -= 1
            if alist[k] < 0:
                return False
        except KeyError:
            return False
    return True

'Counter' being better understood as 'Multiset'.

If m = len(alist) and n = len(sublist), looks to be roughly O(m+n).

Cheers - Chas

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

#11511

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

def contains(alist, sublist):
    alist = Counter(alist)
    for k in sublist:
        try:
            alist[k] -= 1
            if alist[k] < 0:
                return False
        except KeyError:
            return False
    return True

'Counter' being better understood as 'Multiset'.

If m = len(alist) and n = len(sublist), looks to be roughly O(m+n).

Cheers - Chas

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

#11529

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.

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



-- 
Steven

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web