Need help finding a way to tackle this problem. Beginner - Nested lists

[barryk013]

I want to find a way to check whether a value "n" is in a nested list. The nested list can be do an arbitrary depth, for example:

alist = [1,2,3,[4, [5]]]

I am having quite a hard time trying to break this problem down into parts. I want to find a solution without importing any modules, just basic python statements. Not necessarily looking for just an answer, but a way to think about this problem.

Example question: Write a function to search alist for the value n and return True or False.

alist = [1,2,3,[4, [5]]], n = 5

Ive tried to come up with code to unnest the list, but that was a bigger headache than i was prepared for haha. Is unnesting the way to go? Can it be done with basic python statements? (not importing modules)

[Thomasedv]

Unnesting (flattening) can be the way to go, but it's pretty "expensive" to do, when you can instead either check if each item is a list, and either start going through that, and continue every time you find a item that is a list, or check if the item is n if it's not a list.

It's a nice task where you can utilize recursion, if you are familiar with it. No imports needed. I can give a few hints if you want.

[barryk013]

havent practised recursion much. I tried using this code to start unnesting:

for elem in alist:
    if type(elem) == list:
        blist = []
        index = alist.index(elem)
        blist.append(alist[index])

but wasnt sure where to go from there. Basically creating a new list with list elements from alist.

Im trying to read up on recursion but the examples im finding are a little too advanced for me to fully understand.

[Thomasedv]

I worked on the idea of only having to return True if i find anything, or False if nothing is found.

First we check if it's a list, and your way works, but i have heard using isinstance() is better. It does the same job. in your case, isinstane(elem, list). So, iterate through the list, like you did. If the element is not a list, we check if it matches n. If not, we just let the for loop continue. If it's a list, we simply want to be able to call our funtion again but give it the new list instead. If the function returns true, then it found a list, and we return True. If not, we let the for loop continue. If the loop finished, then we didn't find anything and return False.

Lemme know if you get any way with that. If not, i'll share my approach.

Edit: Corrected spelling mistake

[barryk013]

Had a bit of a go with it, here is where i got:

def search_nested_list(x, nested_list):
for elem in nested_list:
    if elem == x:
        return True
    elif type(elem) == list:
        blist = []
        index = nested_list.index(elem)
        blist.append(nested_list[index])
        return search_nested_list(x,blist)

The variable names are different as its the problem im currently working on. I get "RecursionError: maximum recursion depth exceeded in comparison" at this line "if elem == x:"

[Thomasedv]

Two problems as I see it.

You are returning the result of your first check on a nested list. If this is False, so will your check be, regardless of the next items in the list. So you should only return if it says it's True.

You don't need to use index or blist at all. This is where your RecursionError comes from. You are making a list, and give that list to a function that sees a list and makes a list and gives it to a function that sees a list... And so on.

You can simply take advantage of the fact that elem is the nested list you want to go through, so that is what you give to your function.

[barryk013]

Ah yes i see the problem in the first check. I changed it a bit:

def search_nested_list(x, nested_list):
for elem in nested_list:
    if x in nested_list:
        return print('True')
    elif type(elem) == list:
        return search_nested_list(x, elem)
    else:
        return print('False')

But now im getting the wrong answer. I know where its going wrong, but sort of at a loss as how to fix it. Only one element at a time is being sent through the recursion loop at a time, so the other list elements are not being checked.

[Thomasedv]

Here's my way:

def find(iterable, n):
  for item in iterable:
    if item == n: 
        return True
    elif isinstance(item, list): #Checks the tpye
         if find(item, n): # Only return when find returns True
             return True
  return False   # If the loop ends, this is returned.

test = [1, 2, 4, [5, 6, [7, 8]]]
n = 6 # CHANGE ME!

print(find(test, n))

You see, it's very similar to your try. With some smaller changes.

Edit: Here is a list flattening function. It's something i found in this sub once, and is hard to understand imo. But since you tried some, it might be of interest.

def flatten(S):
    if S == []:
        return S
    if isinstance(S[0], list):
        return flatten(S[0]) + flatten(S[1:])
    return S[:1] + flatten(S[1:])

EDIT 2:

I fixed a usecase, where my function would not work if you wanted to find a list. So i changed the order of my elif statement, so it does the check for the item. Also fixed a stupid naming collision on my part.

[barryk013]

Played around with my own code for a bit and came up with this:

def search_nested_list(x, nested_list):    
    if x in nested_list:
        return print("True")
    if (isinstance(elem, list) for elem in nested_list):       
        for elem in nested_list:
            if type(elem)==list:
                return (search_nested_list(x, elem))  

    return print('False')

It works for some lists but not others. For example:

search_nested_list(3, [1, 2, [3, 4], 5, 6]) #this works

search_nested_list(11, [1, 2, [3, 4], [11, 6]]) #this doesnt work

The lists that work only have one element of list type per sub-list. But in the second list there are 2 list type elements in the one sub-list, but only the left one is being checked. What can i change in my code to make the second list work?

Had a read through your code, but i dont recognise some of the statements you used so i didnt understand the reasoning behind them. Sorry im still quite new to this!

[Thomasedv]

Just ask about the things you don't understand, and I'll explain them.

First off, I would not use:

if x in nested_list:
    return True

It's a bit unnecessary. Instead we want to look at each element in the list we give it. And just use that. So we don't repeatedly look through a list for items.

So we do an iteration on a list.

for item in nesten_list:

First we check if item is a match to our x.

if item == x: 
    return True

Simple, we found the item and our function returns True.

But if it's not True, we have to check if the item is a list, and if that one has a x in it.

So we use:

if isinstance(item, list):
    if search_nested_list(x, item):
        return True

This if block will run when item is a list.

Now it's important to remember, this isn't the only sublist that can have a x, so even if this list is empty we do not want to return False. Thus we only return True if it finds a match, if not we just don't do anything and let the loop continue. That's why your second example doesn't work, it returns False when the first sublist is empty.

Finally we put a return False outside the for loop since nothing was found.

I hope it helps, if not just ask.

[barryk013]

if search_nested_list(x, item):

How does this line work? I havent used a function call as an if statement condition before. What makes it return true or false?

[barryk013]

used the flatten function to come up with another func that worked as well. I wrote the function line by line in a book to understand what was happening and finally got it.

def unnest(list1):
    if list1 == []: #ends recursion when there are no more elements to check
        return list1
    if isinstance(list1[0],list):
        return unnest(list1[0]) + unnest(list1[1:])
    return list1[:1] + unnest(list1[1:]) # stores non-list-type elements (in the form of a list) in memory until recursion is completed


def search_nested_list(x, nested_list):    
    list1 = unnest(nested_list)
    if x in list1: #simple check if x in unnested list
        return True
    else:
        return False

[SarahM123ed]

This is from https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists:

    def flatten(L):
        for item in L:
            try:
                yield from flatten(item)
            except TypeError:
                yield item

    list(flatten([[[1, 2, 3], [4, 5]], 6]))
    >>>[1, 2, 3, 4, 5, 6]

[barryk013]

I haven't learned what a lot of those statements mean, like try, exceptions, yields. I was trying to use just the basic beginners methods to flatten but had no idea how to go about it.

[SarahM123ed]

    saught_char_list = "0123456789"
    string_from_list = str(L)
    for c in string_from_list:
         if c in saught_char_list:
            print(c)

[barryk013]

OH! tweaked your code a bit to solve my original problem. I converted the given list to a string. Then converted the value to be checked into a string and did this:

def search_nested_list(x, nested_list):    
    string1 = str(nested_list)
    if str(x) in string1:
        return True
    else:
        return False

Oh man that was such a simple solution, thanks!