Efficient algorithm to get the lowest index of unique elements in a 3d list

user_2205969 0
Viewed 83

Setup

Given a list of lists of lists, such as the one below:

lll = []
for _ in range(5):  
    ll = [random.sample(range(1, 20), 5),
         random.sample(range(1, 20), 5),
         random.sample(range(1, 20), 5)]
    lll.append(ll)

Which might give:

[[[1, 15, 12], [8, 5, 13], [1, 9, 12]],
 [[4, 1, 19], [11, 18, 3], [8, 14, 6]],
 [[17, 8, 4], [1, 16, 3], [19, 13, 11]]]

End Goal

I want to get the lowest index that an element appears, and return this output in the form of a dictionary, e.g.: 

{0: {1, 17, 19, 4, 8, 11}, 1: {5, 9, 13, 14, 15, 16, 18}, 2: {3, 12, 6}}

For example, in lll above, 8 appears in 3 sublists. But it's lowest position in a single sub-list is at 0, which is why it's in the final dictionary at key 0.

Constraint

I must iterate over lll (my use-case assumes that I do not know the full lll). Therefore the traversal_dct will build up over time. The lll seen above is dummy data for demonstration purposes.

Working Solution

This current approach works, but I'm sure it could be more efficient. 

traversal_dct = {}

for ll in lll:

    llT = [*map(list, zip(*ll))]

    for i,xs in enumerate(llT):
        if i not in traversal_dct.keys():
            traversal_dct[i] = set()
        traversal_dct[i] = traversal_dct[i].union(set(xs))

    for i1,key1 in enumerate(traversal_dct.keys()):
        for i2,key2 in enumerate(traversal_dct.keys()):
            if i2 > i1:
                traversal_dct[i2] = traversal_dct[i2] - traversal_dct[i1]
sorting algorithm python
3 Answers

I think you're making this harder than it needs to be.

However many dimensions you have, flatten it to 2D; you're not using anything deeper than a list of 3-element lists.

Now simply make a list of sets, the elements in each dimension

e = [set(row[col] for row in 2d_list) for col in range(len(2d_list[0]))]

Now, from each of these sets, subtract (set difference) each of the previous sets.

e[1] -= e[0]
e[2] -= e[0] + e[1]

... which you can also parameterize in a loop.

user_47851850

IIUC, you could do the following:

lll = [[[1, 15, 12], [8, 5, 13], [1, 9, 12]],
       [[4, 1, 19], [11, 18, 3], [8, 14, 6]],
       [[17, 8, 4], [1, 16, 3], [19, 13, 11]]]


def flatten(lst):
    """Flatten an arbitrary nested list, if the element is not a list return its position"""
    for i, e in enumerate(lst):
        if isinstance(e, list):
            yield from flatten(e)
        else:
            yield (i, e)


# create a dictionary of value -> min-pos
d = {}
for i, e in flatten(lll):
    d[e] = i if e not in d else min(d[e], i)

# reverse the dictionary
reverse = {}
for key, value in d.items():
    reverse.setdefault(value, []).append(key)

print(reverse)

Output

{0: [1, 8, 4, 19, 11, 17], 1: [15, 5, 13, 9, 18, 14, 16], 2: [12, 3, 6]}

If you want to transform the list into a set:

result = {key : set(value) for key, value in reverse.items()}
print(result)

Output

{0: {1, 4, 8, 11, 17, 19}, 1: {5, 9, 13, 14, 15, 16, 18}, 2: {3, 12, 6}}
user_40015920

You can maintain 2 dictionaries:

  • One for keeping track of minimum indices for each value
  • One for keeping track of index -> value set mappings

Then, for each ll that you retrieve, you can update both in time proportional to length of (flattened) ll without having to reconstruct the entire traversal_dict dictionary:

from collections import defaultdict

min_pos = defaultdict(int)
traversal_dict = defaultdict(set)

for ll in lll:  # assume this is streamed / iterated
    for l in ll:
        for (i, val) in enumerate(l):
            if val not in min_pos:  # O(1) to update both dictionaries
                min_pos[val] = i
                traversal_dict[i].add(val)
            elif i < min_pos[val]:
                traversal_dict[min_pos[val]].remove(val)
                min_pos[val] = i
                traversal_dict[i].add(val)
    print traversal_dict  # retrieve answer after each iteration

Output (for the given lll in your question after each iteration):

defaultdict(<class 'set'>, {0: {8, 1}, 1: {9, 5, 15}, 2: {12, 13}})
defaultdict(<class 'set'>, {0: {8, 1, 11, 4}, 1: {5, 9, 14, 15, 18}, 2: {3, 6, 12, 13, 19}})
defaultdict(<class 'set'>, {0: {1, 4, 8, 11, 17, 19}, 1: {5, 9, 13, 14, 15, 16, 18}, 2: {3, 6, 12}})
user_18226980
Related