2.11 Finding the Deep Index of an Item in an Embedded Sequence

Credit: Brett Cannon

2.11.1 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].

2.11.2 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)

2.11.3 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 within the nested sequence. The recipe is coded to work with Python 2.0 or later.

The nested helper function is recursive. helper iterates on its argument sequence, examining each item. When the current item equals goal, the search is finished, and helper breaks out of whatever number of levels of recursion it's in, using the following statement:

raise Found, index_list+[index]

When the current item is a nested sequence, helper calls itself recursively on the subsequence, with an updated index_list. If the recursive call returns normally, that branch of the search has proved fruitless (successful searches don't return normally, but rather raise a Found exception), so helper keeps looking. Note that helper checks for nested sequences via type tests for tuples and lists specifically; see Recipe 1.13 for alternative ways to perform this check.

This recipe is an interesting, although controversial, show-off for the concept of raising an exception as a way to return a value from deeply nested recursive calls. If using exceptions as building blocks for alternative control structures is ever appropriate, this case for their application surely would be. We avoid having to arrange some artificial means of signaling "found" versus "not found," and, even better, we avoid having to arrange for the complexity of returning from a deep stack of calls when the item has been found. In any case, this usage surely underscores how, in Python, exceptions can be used for conditions that are not errors, and indeed not even truly exceptional.

2.11.4 See Also

Recipe 1.13; documentation for the range built-in function in the Library Reference.