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.

is the depth of the nesting arbitrary? or will it be at max, say, 2? — Ma0, Apr 20 '18 at 06:15
first you have list of nested tuples not nested lists in your example :D — Drako, Apr 20 '18 at 06:15
I recommend first go to python.org - read some docs of python types etc. — Drako, Apr 20 '18 at 06:16
they do correct, because in a there is no (1,1), in a there is a tuple of ((1,1),(0,0)) — Drako, Apr 20 '18 at 06:18
you can do: for element in a check if x in element to get True for your cases(but as asked by @Ev. Kounis - depth has to be taken into account — Drako, Apr 20 '18 at 06:19
also nested lists would look like: a = [[[1,1],[0,0]], [3,4]] — Drako, Apr 20 '18 at 06:21
You have to implement it yourself. There are no Python built-in for that. Then, are you struggling in implementing it (if so, how?) — user202729, Apr 20 '18 at 06:21
I guess a recursive approach would be better if depth is not known. — BcK, Apr 20 '18 at 06:26

juanpa.arrivillaga · Answer 1 · 2018-04-20T06:43:53.387

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...

Recursion definitely is a good solution for this. The logic can be written shorter though: def is_in(x, nested): if not isinstance(nested, (tuple, list)): return False if x in nested: return True for item in nested: return is_in(x, item) return False — Lukisn, Apr 20 '18 at 06:45
@Lukisn pretty sure that would't check the entire sublist, since you return on the first iteration fo the for-loop, but I can't tell exactly what you mean without indentation. So consider `a = [((1, 1), (0, 0)), (3, 4), ((8, 8), 10)]` and `is_in((8,8), a)` — juanpa.arrivillaga, Apr 20 '18 at 06:53

Joe Iddon · Accepted Answer · 2018-04-20T06:40:01.877

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

I like the use of `any`, but I think using a conditional expression makes this a tad too unwieldy, I would just do `if: ... else:...` and keep your `any`. You should definitely use `isinstance` though... — juanpa.arrivillaga, Apr 20 '18 at 06:45

M.H Mighani · Answer 3 · 2018-04-20T09:07:38.273

i tried to solve your problem by recursive function method and global variable defining , i wish this solution can give you idea:

a = [((1,1),(0,0)), (3,4)]
global bb
bb=False

def checker(tuple1, tuple2):
    b=str(type(('a','b')))
    for i in range(len(tuple1)):
        if(str(type(tuple1[i]))!=b):
            if (tuple1==tuple2):
                global bb
                bb=True


        else:
            checker(tuple1[i],tuple2)

checker(a,(1,1))
print(bb)
#-->True

bb=False
checker(a,(3,4))
print(bb)
#-->True

bb=False
checker(a,(0,0))
print(bb)
#--->True

bb=False
checker(a,(10,1))
print(bb)
#--->False

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

3 Answers3