1
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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)}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.