Python Cookbook

Finding the Deep Index of an Item in an Embedded Sequence

Credit: Brett Cannon

Problem

You need to find the deep index of an item in an embedded sequence (i.e., the sequence of indexes that will reach the item when applied one after the other to peel off successive layers of nesting). For example, the 6 in [[1,2],[3,[4,[5,6]]],7,[8,9]] has the deep index of [1,1,1,1].

Solution

Lists can be nested (i.e., items of lists can, in turn, be lists), but it takes some care to unnest them when we need to reach for an item:

import sys, types

class Found(Exception): pass

_indices = xrange(sys.maxint)

def _is_sequence(obj):
    return isinstance(obj, types.ListType) or isinstance(obj, types.TupleType)

def deepindex(sequence, goal, is_subsequence=_is_sequence):
    """ deepindex(sequence, goal) -> index list """
    def helper(sequence, index_list, goal=goal):
        for item, index in zip(sequence, _indices):
            if item==goal:
                raise Found, index_list+[index]
            elif is_subsequence(item):
                helper(item, index_list+[index])

    try: helper(sequence, [])
    except Found, index_list: return index_list
    else: return -1

if _ _name_ _=='_ _main_ _':
    print deepindex([[1,2],[3,[4,[5,6]]],7,[8,9]], 6)
    print deepindex([[1,2],[3,[4,[5,6]]],7,[8,9]], 66)

Discussion

This recipe is handy when you have deeply nested sequences and thus need something better than somelist.index(item) to get the index with which an item can be retrieved from the list. It also works as a way to determine if an item is in a deep sequence, regardless of the item’s location ...