CODEWITHSUNDEEP
python-2.7recursion
user2486927
user2486927

Reputation: 13

get deepest nested list

new programmer here. Forgive any occasional idiocy.

I'm trying to write a little function that returns the deepest list in an (arbitrarily large) nested list. The sublists contain tuples, and strings as well.

Example:

L = ['o', ([], [(1, 'V'), (-1, 'C')]), ['o', ['o', (['prefers'], [(1, 'D'), (1, 'D'), (-1, 'V')]), ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]], ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['king'], [(-1, 'N')])]]]

I realize this is insanely hard to parse. Which is um, why I want the machine to do it.

(In case you're wondering, I'm a linguist, and this list defines the derivation tree of a sentence in a minimalist grammar.) What I want is to return the most deeply embedded list, in this case ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]]. Here's what I've tried (among other things):

def get_deepest(L):
    is_list = True
    while is_list == True:
        for e in L:
            is_list = any(isinstance(e,list) for e in L)
            get_deepest(e)
        return e

This hits the recursion limit. Any pointers? I've been struggling with this for a few days.

Thanks.

Upvotes: 1

Views: 996

Answers (3)

ruben2020
ruben2020

Reputation: 1549

Here's my solution. Your get_deepest() call was not returning anything back, so there is a logical error, and it keeps going deeper.

Lst = ['o', ([], [(1, 'V'), (-1, 'C')]), ['o', ['o', (['prefers'], [(1, 'D'), (1, 'D'), (-1, 'V')]), ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]], ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['king'], [(-1, 'N')])]]]

def get_dpst(L, maxdepth):
    deepest_tup = (L, maxdepth)
    for e in L:
        is_list = any(isinstance(e,list) for e in L)
        if is_list:
            tup = get_dpst(e, maxdepth+1)
            if tup[1] > deepest_tup[1]:
                deepest_tup = tup
    return deepest_tup

def get_deepest(L):
    tup = get_dpst(L, 0)
    return tup[0]

def printlist(lst):
    print '[%s]' % ', '.join(map(str, lst))

printlist(get_deepest(Lst))

Or define a function within a function.

Lst = ['o', ([], [(1, 'V'), (-1, 'C')]), ['o', ['o', (['prefers'], [(1, 'D'), (1, 'D'), (-1, 'V')]), ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]], ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['king'], [(-1, 'N')])]]]

def get_deepest(L):
    def get_dpst(L, maxdepth):
        deepest_tup = (L, maxdepth)
        for e in L:
            is_list = any(isinstance(e,list) for e in L)
            if is_list:
                tup = get_dpst(e, maxdepth+1)
                if tup[1] > deepest_tup[1]:
                    deepest_tup = tup
        return deepest_tup
    tup = get_dpst(L, 0)
    return tup[0]

def printlist(lst):
    print '[%s]' % ', '.join(map(str, lst))

printlist(get_deepest(Lst))

Upvotes: 0

user2134086
user2134086

Reputation: 

L = ['o', ([], [(1, 'V'), (-1, 'C')]), ['o', ['o', (['prefers'], [(1, 'D'), (1, 'D'), (-1, 'V')]), ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]], ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['king'], [(-1, 'N')])]]] 
max_depth = -1
deepest_list = None
def get_deepest(L,depth=0):
    global max_depth, deepest_list
    if depth > max_depth:
        max_depth = depth
        deepest_list = L
    for x in L:
        if isinstance(x,list):
            get_deepest(x,depth+1)
get_deepest(L)
print deepest_list

This code is hacked together, and there's bound to be a way to do it without globals. By the way, I think recursion is okay for moderately sized problems here.

Upvotes: 0

deufeufeu
deufeufeu

Reputation: 1008

Mimick the recursion stack by using a stack yourself.

tovisit = [ L ]
current_deepest = None
while tovisit != []:
     v = tovisit.pop()
     for e in v:
         tovisit.append(e)

You'll need to add your own logic here (your current function is wrong, you return e while out of the for loop).

Upvotes: 1

Related Questions