Check if an item is in a nested list

Question

in a simple list following check is trivial:

x = [1, 2, 3]

2 in x  -> True

but if it is a list of list, such as:

x = [[1, 2, 3], [2, 3, 4]]

2 in x   -> False

how can this be addressed in order to return True?

Answer 1

Try this, using the built-in any function. It's the most idiomatic solution, and it's also efficient, because any short-circuits and stops as soon as it finds the first match:

x = [[1, 2, 3], [2, 3, 4]]
any(2 in sl for sl in x)
=> True

Answer 2

Here's a recursive version that works for any level of nesting.

def in_nested_list(my_list, item):
    """
    Determines if an item is in my_list, even if nested in a lower-level list.
    """
    if item in my_list:
        return True
    else:
        return any(in_nested_list(sublist, item) for sublist in my_list if isinstance(sublist, list))

Here are a few tests:

x = [1, 3, [1, 2, 3], [2, 3, 4], [3, 4, [], [2, 3, 'a']]]
print in_nested_list(x, 2)
print in_nested_list(x, 5)
print in_nested_list(x, 'a')
print in_nested_list(x, 'b')
print in_nested_list(x, [])
print in_nested_list(x, [1, 2])
print in_nested_list(x, [1, 2, 3])

True
False
True
False
True
False
True

Answer 3

You can use set.issubset() and itertools.chain():

In [55]: x = [[1, 2, 3], [2, 3, 4]]

In [56]: {4}.issubset(chain.from_iterable(x))
Out[56]: True

In [57]: {10}.issubset(chain.from_iterable(x))
Out[57]: False

You can also chek the membership for multiple items efficiently:

In [70]: {2, 4}.issubset(chain.from_iterable(x))
Out[70]: True

In [71]: {2, 4, 10}.issubset(chain.from_iterable(x))
Out[71]: False

Answer 4

This would work:

for arr in x:
    if 2 in arr:
        print True
        break

I would recommend Oscar's answer as any is the right option here.

Answer 5

TL;DR

x = [0, [1, 2, 3], [2, 3, [4, 5, [6], []], [7, 8]]]
def find_n(input_list, n):
    for el in input_list:
        if el == n or (isinstance(el, list) and find_n(el, n)):
            return True
    return False
print(find_n(x, 6))

Note that, somewhat interestingly:

def find_n(input_list, n):
    return any([el == n or (isinstance(el, list) and find_n(el, n)) for el in input_list])
return (find_n(x, 6))

Is over 50% slower to execute.

Original Answer(s)

What if you have a depth greater than 2? Here's one approach to the generic case:

x = [0, [1, 2, 3], [2, 3, [4, 5, [6], []], [7, 8]]]

def flatten(input_list):
    flat_list = []
    for sublist_or_el in input_list:
        if isinstance(sublist_or_el, list):
            for sublist_or_el2 in flatten(sublist_or_el):
                flat_list.append(sublist_or_el2)
        else:
            flat_list.append(sublist_or_el)
    return flat_list

print(6 in flatten(x))

Not sure about speed though, but as I said, it's one approach that may be useful to someone!

EDIT - BETTER (FASTER) ANSWER:

This reduces the time taken (if n is found, actually even if it is not found, about half the time actually...) by returning early. This is slightly faster than @Curt F.'s answer, and slower than creating a function that assumes a maximum depth of 2 (the accepted answer).

x = [0, [1, 2, 3], [2, 3, [4, 5, [6], []], [7, 8]]]
def find_n(input_list, n):
    flat_list = []
    for sublist_or_el in input_list:
        if isinstance(sublist_or_el, list):
            if find_n(sublist_or_el, n) == True:
                return True
        elif sublist_or_el == n:
            return True
    return False
print(find_n(x, 6))

---

Quick timing (very hacky, sorry, busy today!):

import time

x = [0, [1, 2, 3], [2, 3, [4, 5, [6], []], [7, 8]]]

def a():
    def flatten(input_list):
        flat_list = []
        for sublist_or_el in input_list:
            if isinstance(sublist_or_el, list):
                for sublist_or_el2 in flatten(sublist_or_el):
                    flat_list.append(sublist_or_el2)
            else:
                flat_list.append(sublist_or_el)
        return flat_list
    return (6 in flatten(x))

def b():
    def find_n(input_list, n):
        flat_list = []
        for sublist_or_el in input_list:
            if isinstance(sublist_or_el, list):
                if find_n(sublist_or_el, n) == True:
                    return True
            elif sublist_or_el == n:
                return True
        return False
    return (find_n(x, 6))


zz = 0
for i in range(100000):
    start_time = time.clock()
    res = a()
    zz += time.clock() - start_time
print(a())
print((zz)/100, "seconds")

zz = 0
for i in range(100000):
    start_time = time.clock()
    res = b()
    zz += time.clock() - start_time
print(b())
print((zz)/100, "seconds")

Answer 6

The Óscar Lopez answer is so great! I recommend to use it.

However, you can use itertools to flatten the list and eval it, so:

import itertools

x = [[1, 2, 3], [2, 3, 4]]
2 in itertools.chain.from_iterable(x)

Output: True

Also, you can make it "manually" through comprehension:

x = [[1, 2, 3], [2, 3, 4]]
2 in [item for sub_list in x for item in sub_list]

Output: True

These're only other ways to make it, good luck.

Answer 7

try

 2 in [i for sublist in x  for i in sublist]

Answer 8

My code is based on Óscar López's solution. His solution wasn't exactly what I needed for my problem but it gave enough info for me to figure out my problem. So if you have nested elements in one list and need to see if they're in another nested list, this would work.

#!python2

lst1 = [['a', '1'], ['b', '2'], ['c', '3'], ['d', '4'], ['e', '5']]
lst2 = [['b', '2'], ['d', '4'], ['f', '6'], ['h', '8'], ['j', '10'], ['l', '12'], ['n', '14']]

# comparing by index 0, prints lst1 items that aren't in lst2
for i in lst1:
    if not any(i[0] in sublst for sublst in lst2):
        print i
'''
['a', '1']
['c', '3']
['e', '5']
'''

print

# comparing by index 0, prints lst2 items that aren't in lst1
for i in lst2:
    if not any(i[0] in sublst for sublst in lst1):
        print i
'''
['f', '6']
['h', '8']
['j', '10']
['l', '12']
['n', '14']
'''