Python. Manipulation with a list of dictionaries

Question

Friends, I have a list of dictionaries:

my_list = 
[
{'oranges':'big','apples':'green'},
{'oranges':'big','apples':'green','bananas':'fresh'},
{'oranges':'big','apples':'red'},
{'oranges':'big','apples':'green','bananas':'rotten'}
]

I want to create a new list where partial duplicates are eliminated.

In my case this dictionary must be eliminated:

{'oranges':'big','apples':'green'}

, because it duplicates longer dictionaries:

{'oranges':'big','apples':'green','bananas':'fresh'}
{'oranges':'big','apples':'green','bananas':'rotten'}

Hence, the desired result:

[
{'oranges':'big','apples':'green','bananas':'fresh'},
{'oranges':'big','apples':'red'},
{'oranges':'big','apples':'green','bananas':'rotten'}
]

How to do it? Thanks a million!

Answer 1

The first [well, second, with some edits..] thing that comes to mind is this:

def get_superdicts(dictlist):
    superdicts = []
    for d in sorted(dictlist, key=len, reverse=True):
        fd = set(d.items())
        if not any(fd <= k for k in superdicts):
            superdicts.append(fd)
    new_dlist = map(dict, superdicts)
    return new_dlist

which gives:

>>> a = [{'apples': 'green', 'oranges': 'big'}, {'apples': 'green', 'oranges': 'big', 'bananas': 'fresh'}, {'apples': 'red', 'oranges': 'big'}, {'apples': 'green', 'oranges': 'big', 'bananas': 'rotten'}]
>>> 
>>> get_superdicts(a)
[{'apples': 'red', 'oranges': 'big'}, 
 {'apples': 'green', 'oranges': 'big', 'bananas': 'rotten'}, 
 {'bananas': 'fresh', 'oranges': 'big', 'apples': 'green'}]

[Originally I was using a frozenset here, thinking I could do some kind of clever set operation but obviously didn't come up with anything.]

Answer 2

Try the following implementation

Note in my implementations, I am presorting and selecting only the 2 pair combinations to reduce the number of iterations. This will ensure that the key is always less or equal in size to the hay

>>> my_list =[
{'oranges':'big','apples':'green'},
{'oranges':'big','apples':'green','bananas':'fresh'},
{'oranges':'big','apples':'red'},
{'oranges':'big','apples':'green','bananas':'rotten'}
]

#Create a function remove_dup, name it anything you want
def remove_dup(lst):
    #import combinations for itertools, mainly to avoid multiple nested loops
    from itertools import combinations
    #Create a generator function dup_gen, name it anything you want
    def dup_gen(lst):
        #Now read the dict pairs, remember key is always shorter than hay in length
        for key, hay in combinations(lst, 2):
            #if key is in hay then set(key) - set(hay) = empty set
            if not set(key) - set(hay):
                #and if key is in hay, yield it
                yield key
    #sort the list of dict based on lengths after converting to a item tuple pairs
    #Handle duplicate elements, thanks to DSM for pointing out this boundary case
    #remove_dup([{1:2}, {1:2}]) == []
    lst = sorted(set(tuple(e.items()) for e in lst), key = len)
    #Now recreate the dictionary from the set difference of
    #the original list and the elements generated by dup_gen
    #Elements generated by dup_gen are the duplicates that needs to be removed
    return [dict(e) for e in set(lst) - set(dup_gen(lst))]

remove_dup(my_list)
[{'apples': 'green', 'oranges': 'big', 'bananas': 'fresh'}, {'apples': 'green', 'oranges': 'big', 'bananas': 'rotten'}, {'apples': 'red', 'oranges': 'big'}]

remove_dup([{1:2}, {1:2}])
[{1: 2}]

remove_dup([{1:2}])
[{1: 2}]

remove_dup([])
[]

remove_dup([{1:2}, {1:3}])
[{1: 2}, {1: 3}]

---

A faster implementation

def remove_dup(lst):
    #sort the list of dict based on lengths after converting to a item tuple pairs
    #Handle duplicate elements, thanks to DSM for pointing out this boundary case
    #remove_dup([{1:2}, {1:2}]) == []
    lst = sorted(set(tuple(e.items()) for e in lst), key = len)
        #Generate all the duplicates
    dups = (key for key, hay in combinations(lst, 2) if not set(key).difference(hay))
    #Now recreate the dictionary from the set difference of
    #the original list and the duplicate elements
    return [dict(e) for e in set(lst).difference(dups)]

Answer 3

Here's one implementation you can use: -

>>> my_list = [
{'oranges':'big','apples':'green'},
{'oranges':'big','apples':'green','bananas':'fresh'},
{'oranges':'big','apples':'red'},
{'oranges':'big','apples':'green','bananas':'rotten'}
]

>>> def is_subset(d1, d2):
        return all(item in d2.items() for item in d1.items())
        # or
        # return set(d1.items()).issubset(set(d2.items()))

>>> [d for d in my_list if not any(is_subset(d, d1) for d1 in my_list if d1 != d)]
[{'apples': 'green', 'oranges': 'big', 'bananas': 'fresh'}, 
 {'apples': 'red', 'oranges': 'big'}, 
 {'apples': 'green', 'oranges': 'big', 'bananas': 'rotten'}]

For each dict d in my_list: -

any(is_subset(d, d1) for d1 in my_list if d1 != d)

checks whether, it is a subset of any of the other dict in the my_list. If it returns True, then at least one dict is there, whose subset is d. So, we take a not of it to exclude d from the list.