Finding set difference between two complex dictionaries

Question

Hi,

I have two dictionaries of the following structure:

a) dict1 = {'a':[ [1,2], [3,4] ], 'b':[ [1,2],[5,6] ]}
b) dict2 = {'a':[ [1,2], [5,6] ], 'b':[ [1,2],[7,8] ]}

I need to find the set difference between each key in the dictionary i.e., dict1['a'] - dict2['a'] should return [3,4]. Any thought is appreciated.

Answer 1

The use of mutable items (such as lists) makes the problem MUCH harder, as it precludes the simple use of Python's set data structure. It may be worth making temporary copies/versions which actually use tuples in lieu of those pesky lists:

def tempaux(d):
  return dict((k, set(tuple(x) for x in v))
              for k, v in d.iteritems())

Now:

def thedifs(dd1, dd2)
  d1 = tempaux(dd1)
  d2 = tempaux(dd2)
  allkeys = set(d1).update(d2)
  empty = set()
  difs = []
  for k in allkeys:
    s1 = d1.get(k, empty)
    s2 = d2.get(k, empty)
    adif = s1 - s2
    if adif: difs.append(adif)
  return difs

This assumes actual set difference rather than symmetric difference etc. You can of course turn back the tuples into lists before returns, &c, depending on your exact requirements.

Answer 2

>>> s1 = set([(1,2), (3,4)])
>>> s2 = set([(1,2), (5,6)])
>>> s1 - s2
{(3, 4)}

Answer 3

You've got the wrong data structure for what you're trying to do.

Use this instead.

dict1 = {'a': [(1, 2), (3, 4)], 'b': [(1, 2), (5, 6)]}
dict2 = {'a': [(1, 2), (5, 6)], 'b': [(1, 2), (7, 8)]}

Life is simpler when you try to do set operations on immutable objects like tuples.

This will transform your list-of-lists into a list-of-tuples.

>>> dict( (key,[tuple(v) for v in dict1[key]]) for key in dict1 )
{'a': [(1, 2), (3, 4)], 'b': [(1, 2), (5, 6)]}

Here's the complete solution.

>>> dict1t= dict( (key,[tuple(v) for v in dict1[key]]) for key in dict1 )
>>> dict2t= dict( (key,[tuple(v) for v in dict2[key]]) for key in dict2 )
>>> set(dict1t['a'])-set(dict2t['a'])
set([(3, 4)])