Find common elements and their frequency in list of dictionaries

Question

I have multiple (~40) lists that contain dictionaries, that I would like to find

which are those list items (in this case dictionaries) that are common in all lists
how many times each unique item appears across all lists.

Some examples of the lists are:

a = [{'A': 0, 'B': 0},
     {'A': 0, 'C': 1},
     {'D': 1, 'C': 0},
     {'D': 1, 'E': 0}]

b = [{'A': 0},
     {'B': 0, 'C': 1},
     {'D': 1, 'C': 0},
     {'D': 1, 'E': 0}]

c = [{'C': 0},
     {'B': 1},
     {'D': 1, 'C': 0, 'E': 0},
     {'D': 1, 'E': 0}]

What I tried so far, it is the following code, but it returned values that were not common in all lists...

def flatten(map_groups):
    items = []
    for group in map_groups:
        items.extend(group)
    return items


def intersection(map_groups):
    unique = []
    items = flatten(map_groups)
    for item in items:
        if item not in unique and items.count(item) > 1:
            unique.append(item)
    return unique

all_lists = [a,b,c]
intersection(all_lists)

What I would expect to get as a result would be:


1. {'D': 1, 'E': 0} as a common item in all lists

2.   {'D': 1, 'E': 0}, 3   
     {'D': 1, 'C': 0}, 2
     {'A': 0, 'B': 0}, 1
     {'A': 0, 'C': 1}, 1
     {'A': 0}, 1
     {'B': 0, 'C': 1}, 1
     {'C': 0},
     {'B': 1},
     {'D': 1, 'C': 0, 'E': 0}

1) You don't need luck to solve it, just thinking :p 2) explain what are "common dicts" 3) show us what you have done so far — limserhane, Jan 15 '21 at 13:29
You mean a *dict* needs to appear in ALL lists to be considered? or just in more than one?... Is this part of a larger code or just an excercise? (important to define the structure of inputs and outputs)... have you tried to build a manual cache/counter?... Most of the time it helps if you provide the "would be result" of your sample data along with an explanation of how that result fulfills all rules — RichieV, Jan 15 '21 at 13:37
@HWSiew bad way to phrase it... I apologize. I meant finding the common list items. I have edited my question for clarity. — Rina, Jan 15 '21 at 14:05

mensi · Accepted Answer · 2021-01-15T20:08:59.307

2

To count things, python comes with a nice class: collections.Counter. Now the question is: What do you want to count?

For example, if you want to count the dictionaries that have the same keys and values, you can do something like this:

>>> count = Counter(tuple(sorted(x.items())) for x in a+b+c)
>>> count.most_common(3)
[((('C', 0), ('D', 1)), 2), ((('D', 1), ('E', 0)), 2), ((('A', 0), ('B', 0)), 1)]

The dictionaries here are converted to tuples with sorted items to make them comparable and hashable. Getting for example the 3 most common back as a list of dictionaries is also not too hard:

>>> [dict(x[0]) for x in count.most_common(3)]
[{'C': 0, 'D': 1}, {'D': 1, 'E': 0}, {'A': 0, 'B': 0}]

edited Jan 15 '21 at 20:08

answered Jan 15 '21 at 13:40

mensi

9,580
2
34
43

Unless OP intends to count the actual dictionaries, which are not hashable and thus not feasible to count with collections – RichieV Jan 15 '21 at 13:47
That would make sense if the dictionaries are very large - but the example data provided seems like they are relatively simple and the conversion to tuples should not be a problem. In that case, I'd argue that expressive, easy to read code is more important than performance. – mensi Jan 15 '21 at 13:49
This is exactly what I was thinking for my second point. Thank you! – Rina Jan 15 '21 at 14:13

Red · Answer 2 · 2021-01-15T14:01:02.397

You can use a nested for loop:

a = [{'A': 0, 'B': 0},
     {'A': 0, 'C': 1},
     {'D': 1, 'C': 0},
     {'D': 1, 'E': 1}]

b = [{'A': 0},
     {'B': 0, 'C': 1},
     {'D': 1, 'C': 0},
     {'D': 1, 'E': 0}]

c = [{'C': 0},
     {'B': 1},
     {'D': 1, 'C': 0, 'E': 0},
     {'D': 1, 'E': 0}]

abc_list = [*a, *b, *c]
abc = list()

for d in abc_list:
    for i in abc:
        if d == i[0]:
            abc[abc.index(i)] = (d, i[1] + 1)
            continue
    abc.append((d, 1))

print(abc)

Output:

[({'A': 0, 'B': 0}, 1),
 ({'A': 0, 'C': 1}, 1),
 ({'D': 1, 'C': 0}, 2),
 ({'D': 1, 'E': 1}, 1),
 ({'A': 0}, 1),
 ({'B': 0, 'C': 1}, 1),
 ({'D': 1, 'E': 0}, 2),
 ({'C': 0}, 1),
 ({'B': 1}, 1),
 ({'D': 1, 'C': 0, 'E': 0}, 1)]

Explanation:

The line

[*a, *b, *c]

unpacks all the values in lists a, b and c into a single list, which \i named abc_list.

The continue statement where I put it means to directly continue to the next iteration of the inner for loop, without reaching abc.append((d, 1)).

The above output answers question 2. For question 1, we can use the built-in max() method on the abc list, with a custom key:

print(max(ABC, key=lambda x:x[1])[0])

Of course, it will only return one dictionary, {'D': 1, 'C': 0}. If you want to print out multiple dictionaries that appear the most frequently:

m = max(abc, key=lambda x:x[1])[1]
for d in abc:
    if d[1] == m:
      print(d[0])

Output:

{'D': 1, 'C': 0}
{'D': 1, 'E': 0}

How does this answer `which are those dictionaries that are common in all lists`? — Aleon, Jan 15 '21 at 13:54

Find common elements and their frequency in list of dictionaries

2 Answers2