Convert 2D list to dict of list of index

Question

I have a 2D list like this:

>>> a = [[8,2,3,4,1,2,1,1,3,1,0,1],
...      [1,2,3,4,1,1,5,1,3,1,1,1],
...      [9,2,3,4,2,1,1,1,3,1,0,1],
...      [1,2,3,4,1,1,1,5,3,1,1,1],
...      [1,2,3,4,1,1,6,1,3,0,1,1]]

I want to convert it to:

 result = {0: {0: [10], 
              1: [4, 6, 7, 9, 11], 
              2: [1, 5], 
              3: [2, 8], 
              4: [3], 
              5: [], 
              6: [], 
              7: [], 
              8: [0]}

Dictionary[index of row] = Dictionary of [numbers from 0 to max] and values as a list of indices of that number in the row of the list

My attempt:

>>> a = [[8,2,3,4,1,2,1,1,3,1,0,1],
...      [1,2,3,4,1,1,5,1,3,1,1,1],
...      [9,2,3,4,2,1,1,1,3,1,0,1],
...      [1,2,3,4,1,1,1,5,3,1,1,1],
...      [1,2,3,4,1,1,6,1,3,0,1,1]]
>>> result = {index_row: {j:[ind for ind, val in enumerate(a[index_row]) if val == j] for j in range(max(a[index_row])+1)} for index_row in range(len(a))}
>>> result
{0: {0: [10], 1: [4, 6, 7, 9, 11], 2: [1, 5], 3: [2, 8], 4: [3], 5: [], 6: [], 7
: [], 8: [0]}, 1: {0: [], 1: [0, 4, 5, 7, 9, 10, 11], 2: [1], 3: [2, 8], 4: [3],
 5: [6]}, 2: {0: [10], 1: [5, 6, 7, 9, 11], 2: [1, 4], 3: [2, 8], 4: [3], 5: [],
 6: [], 7: [], 8: [], 9: [0]}, 3: {0: [], 1: [0, 4, 5, 6, 9, 10, 11], 2: [1], 3:
 [2, 8], 4: [3], 5: [7]}, 4: {0: [9], 1: [0, 4, 5, 7, 10, 11], 2: [1], 3: [2, 8]
, 4: [3], 5: [], 6: [6]}}

How can this be improved? is there a better way to convert:

c = [1,2,3,1,1] # list of numbers

to

d = {0:[], 1:[0,3,4], 2:[1], 3:[2]} #Dictionary of index of the occurrence of the same value.

Answer 1

Your code has two nested loops for each array row, which means that you are having to scan every row multiple times to get your result. You can almost get what you want, but with a linear algorithm, doing the following:

d = {}
for idx, val in enumerate(c):
    d.setdefault(val, []).append(idx)

>>> d
{1: [0, 3, 4], 2: [1], 3: [2]}

This is missing the empty lists for items not present in the original lists. You can create those by doing:

for j in range(max(d.keys())): # Don't need max+1, the max is already there
    d.setdefault(j, [])

>>> d
{0: [], 1: [0, 3, 4], 2: [1], 3: [2]}

If your list has n items, and its max was m, your original algorithm was doing O(n*m) operations, while this will keep that to O(n+m).

Putting the whole thing together for 2D arrays I would put all of the above in a function and then go with a dict comprehension that called it, so something like:

def list2dict(a):
    ret = {}
    for idx, val in enumerate(a):
        ret.setdefault(val, []).append(idx)
    for val in range(max(ret.keys())):
        ret.setdefault(val, [])
    return ret

result = {idx : list2dict(val) for idx, val in enumerate(a)}