testing if a list contains a sublist

ChasBrown cbrown at cbrownsystems.com
Tue Aug 16 02:14:14 EDT 2011


On Aug 15, 4:26 pm, Johannes <dajo.m... at 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



More information about the Python-list mailing list