CODEWITHSUNDEEP
pythonrecursionfunctional-programming
Leo wahyd
Leo wahyd

Reputation: 207

How to find a given element in nested lists?

This is my iterative solution:

def exists(key, arg):
    if not arg:
        return False
    else:
        for element in arg:
            if  isinstance(element,list):
                for i in element:
                    if i==key:
                        return True
            elif element==key:
                return True
    return False
print(exists("f", ["a", ["h", "e", "j"], ["t", "e", "s", "c", "o"]]))

However, my L.A. wants a double recursive function to solve this.

my attempt:

def exists(key, arg):
    if not arg: //base case
        return False
    elif arg[0]==key: //if we find the key from the first trial
        return True
    else:
        return (exists(arg[0:],key))

This doesn't work; it shouldn't, because there is no stop. Also, it does not account for lists of lists; I don't know how to do that.

Any answer, comment, etc. is appreciated

Upvotes: 2

Views: 1868

Answers (5)

Leo wahyd
Leo wahyd

Reputation: 207

Thanks everyone for your help, here is the answer that I have figured out. While it does not look as elegant as most of the answers that were already provided, this answer is the only answer that my lab instructor will accept as it is a pure functional programming method meaning no side effects or for loops:

def exists(key, seq):
    if not seq:
        return False
    elif seq[0]==key:
        return True
    if isinstance(seq[0],list):
        return(exists(key,seq[0]) or exists(key,seq[1:]))

    else:
        return exists(key,seq[1:])
    return False
print(findkey("s", ["g","t", "e", ["s"], ["l","k","s",["d","f"],"w"], "o"]))

Upvotes: 2

molbdnilo
molbdnilo

Reputation: 66451

If we consider these cases:

  • my_list is empty: the key isn't found
  • my_list is not a list: the key isn't found
  • my_list is a non-empty list (two cases):
    • my_list[0] is the key: it was found
    • otherwise, look for the key in both my_list[0] and my_list[1:]

the code would be

def exists(key, my_list):
    if not isinstance(my_list, list) or not my_list:
        return False

    return (my_list[0] == key
            or exists(key, my_list[0]) 
            or exists(key, my_list[1:]))

or even

def exists(key, my_list):
    return (isinstance(my_list, list)
            and len(my_list) > 0 
            and (my_list[0] == key
                 or exists(key, my_list[0])
                 or exists(key, my_list[1:])))

Upvotes: 3

Craig Burgler
Craig Burgler

Reputation: 1779

def exists(k, l):
    if not isinstance(l, list):
        return False
    if k in l:
        return True
    return any(map(lambda sublist: exists(k, sublist), l))

Upvotes: 4

nauer
nauer

Reputation: 700

You are close. You only have to check if arg[0] is a sublist and if make a new call. Next you are missing a loop to run through all items of the list. This should work.

def exists(key, arg):
    for item in arg:
        if isinstance(item, list):
            # Recursive call with sublist
            if exists(key, item):
                return True
        else:
            if item == key:
                return True
    return False

Upvotes: 2

Moinuddin Quadri
Moinuddin Quadri

Reputation: 48090

The logic is to iterate each element in your list and check:

  • if list: call the function again with the sub-list.
  • if equals the key: return True
  • else: return False

Below is sample code to find whether key exists or not in nested list

def exists(key, my_list):
    for item in my_list:
        if isinstance(item, list):
            if exists(key, item):  # <--Recursive Call
                return True
        elif item == key:
            return True
    return False

# Example
>>> my_list = [[[1, 2, 3, 4, 5], [6, 7,]], [8, 9], 10]
>>> exists(2, my_list)
True
>>> exists(6, my_list)
True
>>> exists(8, my_list)
True
>>> exists(10, my_list)
True
>>> exists(11, my_list)
False

Upvotes: 2

Related Questions