How can I find the index for a list of nested lists which I am recursing over?

Question

I'm having some trouble finding a way to get a list index against a list of nested lists.

For example I can find out how many nodes, or the structure of the list for a given node with the following two functions.

t = ['add', [ \
        ['divide a', [ \
            ['if statement', ['Var 9', 'Var 5', 'Var 1', 'Var 4']], \
            ['subtract', [ \
                ['add', [ \
                    ['round to integer', ['Var 10']], 'Var 4'] \
                ], 'Var 9' \
            ]] \
        ]], 'Var 4' \
     ]]

def total_nodes(structure,num_nodes):
    s = structure
    print "N:" , num_nodes , s
    num_nodes += 1
    if isinstance(s,str): return num_nodes    
    if s[1]:
        for x in range(len(s[1])):
            num_nodes = total_nodes(s[1][x], num_nodes)
        return num_nodes 


def get_structure_for_node(structure,counter,find_node=1):
    s = structure
    if not isinstance(counter,int):
        return counter
    if counter == find_node:
        return s
    counter += 1
    if isinstance(s,str): return counter
    if s[1]:
        for x in range(len(s[1])):
            counter = get_structure_for_node(s[1][x],counter,find_node=find_node)
        return counter



print 
print total_nodes(t,0)
print
print get_structure_for_node(t,0,find_node=12)

OUTPUT:

N: 0 ['add', [['divide a', [['if statement', ['Var 9', 'Var 5', 'Var 1', 'Var 4']], ['subtract', [['add', [['round to integer', ['Var 10']], 'Var 4']], 'Var 9']]]], 'Var 4']]
N: 1 ['divide a', [['if statement', ['Var 9', 'Var 5', 'Var 1', 'Var 4']], ['subtract', [['add', [['round to integer', ['Var 10']], 'Var 4']], 'Var 9']]]]
N: 2 ['if statement', ['Var 9', 'Var 5', 'Var 1', 'Var 4']]
N: 3 Var 9
N: 4 Var 5
N: 5 Var 1
N: 6 Var 4
N: 7 ['subtract', [['add', [['round to integer', ['Var 10']], 'Var 4']], 'Var 9']]
N: 8 ['add', [['round to integer', ['Var 10']], 'Var 4']]
N: 9 ['round to integer', ['Var 10']]
N: 10 Var 10
N: 11 Var 4
N: 12 Var 9
N: 13 Var 4
14

Var 9

From the output I can see the path from t to the node '12' we searched for would be:

t[1][0][1][1][1][1]

but I have been unable to find a way to keep track of this index key as I am going through the recursive function. which I require to change elements of the list / tree

Any takers?

I should add that I had been trying to track it by adding in a variable to the recursion which builds a string of where it went i.e.

path = "10112101"

then trying to work with this later, however I've been unable to get it accurate and would prefer a cleaner way.

Haven't looked very carefully at this, but can't you return a list instead of an integer for `counter`, and use `counter.extend(get_structure_for_node(s[1][x],counter,find_node=find_node)`. (Of course, the other return statement should be something like `if isinstance(s,str): return [counter]`.) This would be very similar to your string, but feels 1/ more natural (list instead of string with the indices), and 2/ *returns* the value, instead of having an extra variable in the function declaration. — , Oct 12 '12 at 14:14
As an aside: you don't need to escape a new line in the middle of a list. — Andy Hayden, Oct 12 '12 at 14:19
I didn't escape it when I entered it. it happened when I saved the code snippet — joeButler, Oct 12 '12 at 15:07

score 3 · Accepted Answer · edited May 23 '17 at 11:43

The simplest flatting algorithm is:

def flat_list(l):
    for node in l:
        if isinstance(node, list):
            for i in flat_list(node):
                yield i
        else:
            yield node

It's easy to modify flatting algorithm to keep track:

def flat_list_keeping_track(l, track=None):
    track = track or ()
    for i, node in enumerate(l):
        new_track = track + (i,)
        if isinstance(node, list):
            for result in flat_list_keeping_track(node, track=new_track):
                yield result
        else:
            yield node, new_track

And now you can type

def get_structure_for_node(structure, find_node=1):
    return list(flat_list(structure))[find_node][1]

This is not the fastest way. If your structure is big and you use relatively small 'find_node' values then you should write something like that (based on get-the-nth-item-of-a-generator-in-python):

import itertools
def get_structure_for_node(structure, find_node=1):
    return next(itertools.islice(flat_list(structure), find_node, find_node+1))[1]

You can also modify other flatten function if the speed is really important (see making-a-flat-list-out-of-list-of-lists-in-python or making-a-flat-list-out-of-a-multi-type-nested-list).

Thank you very much! I've plugged in the flat list keeping track and it works perfectly. — joeButler, Oct 12 '12 at 15:05

score 1 · Answer 2 · answered Oct 12 '12 at 14:26

Your approach of keeping a path would work.

However, for your particular problem, it might be more useful (and pythonic) to rewrite your code using a generator.

What this means is that you manage your index inside your function and yield partial results while walking your function.

treewalk(node):
    for n in node.children:
        for result in treewalk(n):
            yield result
    else:
        yield node

How can I find the index for a list of nested lists which I am recursing over?

2 Answers2