Credit: Brett Cannon
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].
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)
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.
Recipe 1.13; documentation for the
range
built-in function in the Library Reference.