The intersection of all combinations of n sets

by

Here is a solution inspired by MapReduce: Simplified Data Processing on Large Clusters, which can therefore be written in a distributed way if you want.

Map all of your elements in sets to pairs [element, set]. Group this list by element. You can just sort and pull out elements. Or you can create a hash of arrays whose keys are the elements and values are the list of sets that element is found in. Then for each element, emit a list of [combination of sets, element]. Group that by combination. And now for each non-empty combination, you can just read off the elements in it.

If you wish to distribute the computation with a real map-reduce, the first map would map to a key of element, and value of set. The first reduce would just store by element the list of sets it is in. The second map would emit for each element one key for each combination of sets it is in, with the element as the value. And the second reduce would store your final answer.

It may help to work your example in detail. You start with:

Set 1 = 1, 10, 6, 11, 14, 3
Set 2 = 3, 7, 11, 9, 5
Set 3 = 11, 6, 9, 1, 4

You map that to the list:

[1, Set 1], [10, Set 1], [6, Set 1], [11, Set 1], [14, Set 1], [3, Set 1],
[3, Set 2], [7, Set 2], [11, Set 2], [9, Set 2], [5, Set 2],
[11, Set 3], [6, Set 3], [9, Set 3], [1, Set 3], [4, Set 3],

Now group by element (I did it by hand by sorting) to get:

1: Set 1, Set 3
3: Set 1, Set 2
4: Set 3
5: Set 2
6: Set 1, Set 3
7: Set 2
9: Set 2, Set 3
10: Set 1
11: Set 1, Set 2, Set 3
14: Set 1

And now we do the second mapping (skipping the elements that are only in one set) to get:

[(Set 1, Set 3), 1],
[(Set 1, Set 2), 3],
[(Set 1, Set 3), 6],
[(Set 2, Set 3), 9],
[(Set 1, Set 2), 11],
[(Set 1, Set 3), 11],
[(Set 2, Set 3), 11],
[(Set 1, Set 2, Set 3), 11]

Group that by combination of sets and we get:

(Set 1, Set 2): 3, 11
(Set 1, Set 3): 1, 6, 11
(Set 2, Set 3): 9, 11
(Set 1, Set 2, Set 3): 11

More Related Contents:

  1. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  2. Computing set intersection in linear time?
  3. Deciding a Big-O notation for an algorithm
  4. What is a plain English explanation of “Big O” notation?
  5. Algorithm to return all combinations of k elements from n
  6. What does O(log n) mean exactly?
  7. How to create the most compact mapping n → isprime(n) up to a limit N?
  8. What exactly does big Ө notation represent?
  9. Reverse the ordering of words in a string
  10. Can hash tables really be O(1)?
  11. Difference between Big-O and Little-O Notation
  12. Time complexity of python set operations?
  13. Time complexity of Euclid’s Algorithm
  14. What would cause an algorithm to have O(log log n) complexity?
  15. What is Constant Amortized Time?
  16. What is the difference between tree depth and height?
  17. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  18. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  19. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  20. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  21. C – How to implement Set data structure?
  22. In Order Successor in Binary Search Tree
  23. What is the advantage to using Bloom filters?
  24. Why does Dijkstra’s algorithm use decrease-key?
  25. Search a sorted 2D matrix [duplicate]
  26. Prove that binary heap build max comparsion is (2N-2)
  27. Algorithm for merging two max heaps?
  28. Why is bubble sort O(n^2)?
  29. Why is vector array doubled?
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment