Let say I have a list of sets, defined like this (3 sets in this example) :
A = [1, 2, 3, 4, 5]
B = [4, 5, 6, 7, 8]
C = [1, 2, 3, 4, 5, 6, 7, 8]
Total number of elements defined in sets : 18
I'd like to find which subsets are common in sets, in order to simplify the sets definition.
In this example, [4, 5] is common to all sets. I can easily find this by applying an intersection between all sets.
Then I can rewrite sets definition like this :
A, B, C = [4, 5]
A = [1, 2, 3]
B = [6, 7, 8]
C = [1, 2, 3, 6, 7, 8]
Total number of elements : 14
However, this can be improved further more :
A, C = [1, 2, 3]
B, C = [6, 7, 8]
A, B, C = [4, 5]
Total number of elements : 8
My question is : is there any algorithm (pseudocode) in order to simplify sets definition like in this example ?
Best Answer
I answered a similar question at https://stackoverflow.com/questions/26028124/the-intersection-of-all-combinations-of-n-sets/26028865#26028865 and the only difference in what you need is that the second map should map an element to the set of sets it is in, rather than every subset of that set.