TransWikia.com

How to find an intersection given a list of lists that contain dictionaries

Stack Overflow Asked on December 7, 2021

Right now I am using method 2 found on https://www.geeksforgeeks.org/python-find-common-elements-in-list-of-lists/ with the code as follows:

# Python3 code to demonstrate  
# common element extraction form N lists  
# using map() + intersection() 
  
# initializing list of lists 
test_list = [[2, 3, 5, 8], [2, 6, 7, 3], [10, 9, 2, 3]] 
  
# printing original list 
print ("The original list is : " + str(test_list)) 
  
# common element extraction form N lists 
# using map() + intersection() 
res = list(set.intersection(*map(set, test_list))) 
  
# printing result 
print ("The common elements from N lists : " + str(res)) 

The original list is : [[2, 3, 5, 8], [2, 6, 7, 3], [10, 9, 2, 3]]

The common elements from N lists : [2, 3]

I want to do the same thing except instead using

test_list = [[dict2,dict3,dict5,dict8],[dict2,dict6,dict7,dict3],[dict10,dict9,dict2,dict3]]

Where,

The original list is :

test_list = [[dict2,dict3,dict5,dict8],[dict2,dict6,dict7,dict3],[dict10,dict9,dict2,dict3]]

The common elements from N lists : [dict2, dict3]

3 Answers

A set need hashable items but dicts are not. Let's define a custom dict class hashable. (I refer to this article. python set of objects with custom hash behavior)

import json

class DictItem(dict):
    """custome dict class hashable"""
    def __hash__(self):
        return hash(frozenset(json.dumps(self, sort_keys=True)))
    
dict2 = DictItem({"foo": [2]})
dict3 = DictItem({"foo": 3})
dict5 = DictItem({"bar": 5})
dict6 = DictItem({"bar": []})
dict7 = DictItem({"bar": 7})
dict8 = DictItem({"bar": 8})
dict9 = DictItem({"baz": 9})
dict10 = DictItem({"quux": 10})

test_list = [[dict2,dict3,dict5,dict8],
             [dict2,dict6,dict7,dict3],
             [dict10,dict9,dict2,dict3]]
res = list(set.intersection(*map(set, test_list))) 
  
# printing result 
print ("The common elements from N lists : " + str(res)) 

Answered by 정도유 on December 7, 2021

dicts are non-hashable, hence set(a_dict) wont work.

Define


class my_dict(dict):

     @classmethod
     def freeze(cls, obj):
          if isinstance(obj, dict):
              obj_with_frozen_values = {k: cls.freeze(v) for k, v in obj.items()}
              # sort on keys to get one specific order
              return frozenset(sorted(obj_with_frozen_values.items(), key=lambda k: k[0]))
          if isinstance(obj, (set, tuple, list)):
              obj_type = str(type(obj))
              frozen_obj = tuple([cls.freeze(v) for v in obj])
              return frozenset((obj_type, frozen_obj))  # add extra info obj type
          return obj

     def __hash__(self):
          return hash(self.freeze(self))

(This should take care of inner values being dict/lists etc themselves)

And then map all dicts to my_dict. Hopefully this should solve the issue.

Answered by vestronge on December 7, 2021

You cannot use the set technique because the elements of a set need to be hashable, and dicts are not. You can do equality comparison testing between dicts, but you will have to do this "by hand". Here is an example solution, where you obtain an intersection by starting with a copy of the first sub-list and then remove items that are not in the remaining sub-lists.

dict2 = {"foo": [2]}
dict3 = {"foo": 3}
dict5 = {"bar": 5}
dict6 = {"bar": []}
dict7 = {"bar": 7}
dict8 = {"bar": 8}
dict9 = {"baz": 9}
dict10 = {"quux": 10}

test_list = [[dict2,dict3,dict5,dict8],
             [dict2,dict6,dict7,dict3],
             [dict10,dict9,dict2,dict3]]

answer = test_list[0].copy()
for lst in test_list[1:]:
    remove_indices = [i for i, item in enumerate(answer) if item not in lst]
    for i in remove_indices[::-1]:
        answer.pop(i)

print(answer)

Prints:

[{'foo': [2]}, {'foo': 3}]

Answered by alani on December 7, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP