I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets.
Set a = [adam, ben, charlie, ...]
Set b = [adam, john, kenny, ...]
Set c = [adam, john, eve, ...]
The algorithm will then get all pair combinations of sets, and count the number of intersections within those pairs.
Set a & b = 1 (adam is in both sets)
Set a & c = 1 (adam is in both sets)
Set b & c = 2 (adam and john is in both sets)
The naïve algorithm I have come up with is:
- Generate all 2-combinations of the sets and put them in a list.
- For each pair in the list, find the intersection of the pair, add the count to the result list
- Repeat for all pairs
Each set can have over 10k elements (strings), and there are over 1k sets. Obviously the performance is horrible since the runtime is exponential.
Are there any methods to improve the runtime? Is there a different algorithm that would improve the calculation? The results doesn't have to be exact, i.e. it can be an estimation.
The task is to find overlapping users from different communities. For example we have different communities 1, 2, 3, etc. each community has their users (usernames in the list). I am trying to find the number of overlapping users from each community. e.g. community 1 shares 200 users with community 2, shares 400 users with community 3, so on and so forth.
x.intersection(y)). the complexity might not be as bad as I thought, but the real world performance is still not that great. $\endgroup$