Data-structure for multiway associativity in Python

[MRAB]

On 2018-01-27 18:01, qrious wrote:
> 
> 
> I need a data structure and a corresponding (hopefully fast) mechanism associated with it to do the following. While I am looking for the concept first, my preference for implementation of this will be in Python.
> 
> [c1, c2,..., cn] is a list of strings (for my own implementation, but could be any other type for the generic problem). There will be many hundreds, if not thousands, of such lists with no shared member.
> 
> The method getAssocList(e) will return lists of the lists for which e is an element.
> 
> Here a hash may be a way to go, but need help in figuring it out. Also, can there be a faster and more memory efficient solution other than hashes?
> 
You could build a dict where the key is the element and the value is a 
list of those lists that contain that element.

The 'defaultdict' class is useful for that.


from collections import defaultdict

assoc_dict = defaultdict(list)

for lst in list_of_lists:
     for elem in lst:
         assoc_dict[elem].append(lst)

# Optionally convert to a plain dict once it's built.
assoc_dict = dict(assoc_dict)