26

Is there any builtins to check if a list is contained inside another list without doing any loop?

I looked for that in dir(list) but found nothing useful.

vvvvv
  • 25,404
  • 19
  • 49
  • 81
Young
  • 7,986
  • 7
  • 43
  • 64

5 Answers5

52

Depends on what you mean by "contained". Maybe this:

if set(a) <= set(b):
    print("a is in b")
vvvvv
  • 25,404
  • 19
  • 49
  • 81
nosklo
  • 217,122
  • 57
  • 293
  • 297
  • Seems functionally equivalent to my solution -- anybody know if either one has a performance advantage? – Etaoin Apr 06 '10 at 06:06
  • Not sure I buy that -- the call to `sub` is linear, but the `<=` can't be free. Am I missing something? – Etaoin Apr 06 '10 at 06:41
  • 7
    @Etaoin: `set` s are hashtables. Therefore the cost to access an object in a `set` is `O(1)`. In this code you have to go through all elements in `set(a)` (`O(len(set(a))`) and check whether this element is in `set(b)` (`O(1)`). But of course the overall cost us not (`O(len(sublist))`) as the sets have to build from the list first. I am not exactly sure what this costs but I think it should be `O(len(list))` so the overall cost is `O(len(a)) + O(len(b)) + O(len(set(a))` – Felix Kling Apr 06 '10 at 06:49
  • Nice! Thanks -- I was missing the constant-time access to sets. +1 to your comment and this answer. (Also, of course, in my last comment, `sub` was a brainfart for `set`.) – Etaoin Apr 06 '10 at 07:06
  • what if `a = [1,1,2,3]` and `b=[1,2,3]` ? `a` is not contained in `b` but your code says so. – Adrien Plisson Apr 06 '10 at 10:17
  • @Adrien Plisson: That's why I said *Depends on what you mean by "contained"*. – nosklo Apr 06 '10 at 11:03
18

Assuming that you want to see if all elements of sublist are also elements of superlist:

all(x in superlist for x in sublist)
vvvvv
  • 25,404
  • 19
  • 49
  • 81
Etaoin
  • 8,444
  • 2
  • 28
  • 44
13

You might want to use a set

if set(a).issubset(b):
    print('a is contained in b')
jesteras
  • 141
  • 1
  • 4
  • Is there any advantage of your answer over [nosklo's answer](https://stackoverflow.com/a/2582917/5376789)? – xskxzr Jun 14 '19 at 08:17
  • 1
    Yes, first there is no need to convert both `list`s to `set`s. Thus, my proposal saves one instruction (I've checked with `dis.dis()`). Also, because of the verbosity of the method `issubset` it is more readable. – jesteras Jun 16 '19 at 17:52
6

the solution depends on what values you expect from your lists.

if there is the possiblity of a repetition of a value, and you need to check that there is enough values in the tested container, then here is a time-inefficient solution:

def contained(candidate, container):
    temp = container[:]
    try:
        for v in candidate:
            temp.remove(v)
        return True
    except ValueError:
        return False

test this function with:

>>> a = [1,1,2,3]
>>> b = [1,2,3,4,5]
>>> contained(a,b)
False    
>>> a = [1,2,3]
>>> contained(a,b)
True
>>> a = [1,1,2,4,4]
>>> b = [1,1,2,2,2,3,4,4,5]
>>> contained(a,b)
True

of course this solution can be greatly improved: list.remove() is potentially time consuming and can be avoided using clever sorting and indexing. but i don't see how to avoid a loop here...

(anyway, any other solution will be implemented using sets or list-comprehensions, which are using loops internally...)

Adrien Plisson
  • 22,486
  • 6
  • 42
  • 73
-1

If you want to validate that all the items from the list1 are on list2 you can do the following list comprehension:

all(elem in list1 for elem in list2)

You can also replace list1 and list2 directly with the code that will return that list

all([snack in ["banana", "apple", "lemon", "chocolate", "chips"] for snack in ["chips","chocolate"])

That any + list comprehension can be translated into this for a better understanding of the code

return_value = False
for snack in snacks:
   if snack in groceries:
     return_value = True
   else:
     return_value = False
Luka H
  • 29
  • 3