Finding the index of an item in a list of lists

Question

If I have this list of lists:

[[1,2,3,4],[5,6,7,8,9,10],[11,12,13]]

How might I be able to find the index of the sublist itself according to the value given?

For example:

If my value is 2, The index returned would be 0

If my value is 9, the index returned would be 1

if my value is 11, the index would be 2

Answer 1

Either use a list-comp as demonstrated by @jrd1 if you want all indices, or if you want just the first occurrence, then:

next((idx for idx, val in enumerate(your_list) if 2 in val), None)

We use None here as a default value instead of raising a StopIteration where the value is not found in any sublist. Remove the default value if you wish the exception raised instead.

Answer 2

Just use enumerate:

l = [[1,2,3,4],[5,6,7,8,9,10],[11,12,13]]

# e.g.: find the index of the list containing 12
# This returns the first match (i.e. using index 0), if you want all matches
# simply remove the `[0]`
print [i for i, lst in enumerate(l) if 12 in lst][0] 

This outputs:

[2]

Edit:

@hlt's comment suggests using the following for more efficient behavior:

next(i for i,v in enumerate(l) if 12 in v)

Answer 3

If you have many queries and/or a dynamic list of lists, then you are better off making a map. Specifically a value:set map. Where you map the value to a set of indices (sub-lists) that contain that value. Though this works best if the list doesn't change.

Example for [[1,2,3,4],[5,6,7,8,9,10], [11,12,13], [1,2,3,4,5,6,7,8,9,10,11,12,13]:

# Code for populating the map
map = collections.defaultdict(set)
index = 0
for i,v in enumerate(l):
    for _ in v:
        map[index].add(i)
        index += 1

# Result:
map = {
    1: {0,3},
    2: {0,3},
    3: {0,3},
    4: {0,3},
    5: {1,3},
    6: {1,3},
    7: {1,3},
    8: {1,3},
    9: {1,3},
    10:{1,3},
    11:{2,3},
    12:{2,3},
    13:{2,3}
}

You can also treat the sub-lists as intervals (covering a range of indices) and allowing for O(log N) look up and O(log N) add/remove sublist/element by building an interval tree. It takes O(L log L) to build the interval tree where L is the number of sublists.