Python nested list recursion search

Question

Given a nested list L (such that each element of L is either an integer, or a list, which may itself contain integers, or lists, which may in turn.... etc) return True i s is in L.

search([1, [2, 3], 4, [5, [6 , [], [8, 9]], 10]], 8)

should return True.

Here is what I have so far:

def search (L,s):
"""(list, anytype) _> Bool
Returns true iff s is present in L
"""
if L:
    if L[0] == s:
        return True
    else:
        return search (L[1:], s)
else:
    return False

This current code works for a list if it isn't nested, or if it is nested like so (the nested element is the last element):

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

But not for the following:

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

How can I change my code so that it works for a nested list? with the nested element being anywhere in the list not strictly the last element?

Appreciate any help!

EDIT: Sorry, forgot to specify that it needs to be recursive.

possible duplicate of [How can I deep search a Python list?](http://stackoverflow.com/questions/15292893/how-can-i-deep-search-a-python-list) — , Feb 09 '14 at 17:47

thefourtheye · Accepted Answer · 2014-02-09T18:17:24.037

6

You can squeeze your entire code like this

def search(current_item, number):
    if current_item == number: return True
    return isinstance(current_item, list) \
        and any(search(item, number) for item in current_item)

You can test it like this

for i in range(12):
    print i, search([1, [2, 3], 4, [5, [6 , [], [8, 9]], 10]], i)

Output

0 False
1 True
2 True
3 True
4 True
5 True
6 True
7 False
8 True
9 True
10 True
11 False

The logic is like this,

If the current_item is equal to the number we are looking for, return True.
If the current_item is not an instance of list, then it is a number in this case. If it is a number and it does not equal to number we should return False.
If the current_item is a list, then go through each and every element of it and check if any of the elements has number. any returns immediately after getting the first True value.

edited Feb 09 '14 at 18:17

answered Feb 09 '14 at 17:47

thefourtheye

233,700
52
457
497

Sorry i forgot to specify I need to use recursion. – Nick Feb 09 '14 at 17:52
3

This *does* use recursion - see the recursive call to `search` on the last line. – Lukas Graf Feb 09 '14 at 17:53
could you explain the last 2 lines of your code? I understand `isinstance` and `any` but I am not exactly sure what they do when put together like that – Nick Feb 09 '14 at 18:05
@NickGong Please check my answer now. I have added basic explanation. – thefourtheye Feb 09 '14 at 18:17

score 2 · Answer 2 · answered Feb 09 '14 at 17:53

2

If it doesn't matter where the item is in the list something like this should work

def unpack(iterable):
   result = []
   for x in iterable:
      if hasattr(x, '__iter__'):
         result.extend(unpack(x))
      else:
         result.append(x)
   return result

 >>> unpack([1,2,3,[4,5,6],7,[8,[9,10],11,]])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

answered Feb 09 '14 at 17:53

user2682863

3,097
1
24
38

This is a good algorithm to have in your commonly used tools. It's too bad the `itertools flatten` recipe doesn't have something like this. Your algorithm might be better as a generator since the list it unpacks could be very large. – IceArdor Feb 09 '14 at 18:26
very interesting, it looks pretty good to me, I would keep this in mind for future reference. But for this exercise I was required to set parameter like that and use recursion. Thank you though! – Nick Feb 09 '14 at 19:20

Python nested list recursion search

2 Answers2

Linked

Related