Python: Check if a nested list is in a nested list

Question

Sorry for for the potentially silly question. But this seems to be a stumping problem I just can't find the answer to.

Say I have the following mixed nested list in python:

a = [((1,1),(0,0)), (3,4)]

I'd like to check if the following tuples b, c and d appear in a:

b = (1,1)
c = (0,0)
d = (3,4)

print(b in a)  # <- False ?
print(c in a)  # <- False ?
print(d in a)  # <- True

I'd like to replace the code in each print statement in such away that the search finds the tuple in the list and as such returns True

Any help at all would be much appreciated. Apologies if this question has already been asked before.

Answer 1

We need a recursive function that takes a list or tuple and an element to find.

Each function should check whether the element is in the current iterable using the in operator. If it is in then return True, otherwise check if it is in any of the lower dimensions by recursively calling itself with each of the lower iterables and return if any of those succeeded (this can be done with a for-loop, but we may as well use the any() function).

So a one liner would be roughly:

def inc(it, e):
    return True if e in it else any(inc(iit, e) for iit in it if type(iit) in (list, tuple))

And it works as intended:

>>> inc(a, (1,1))
True
>>> inc(a, (0,0))
True
>>> inc(a, (3,4))
True

Answer 2

The list has two elements, a tuple which contains other tuples, and a tuple of ints. If you want to check the nested structures, you are going to have to do that yourself. A recursive solution (this one assumes the nested containers can only be either tuple's or lists) would be one option if nesting can be arbitrarily deep:

>>> a = [((1,1),(0,0)), (3,4)]
>>> def is_in(x, nested):
...     result = False
...     if not isinstance(nested, (tuple, list)):
...         return result
...     for item in nested:
...         if x == item:
...             result = True
...         else:
...             result = result or is_in(x, item)
...         if result:
...             return True
...     return result
...
>>> is_in((1,1), a)
True
>>> is_in((0,0), a)
True
>>> is_in((3,4), a)
True
>>> is_in((8, 8), a)
False
>

This should stop traversing once the first match is found.

Note, if recursion isn't your thing, you can replace the call stack with your own stack!

def is_in_iterative(x, nested):
    stack = [nested]
    while stack:
        item = stack.pop()
        print(item)
        if item == x:
            return True
        elif isinstance(item, (list, tuple)):
            stack.extend(item)
    return False

However, note that this will check in the reverse order...