Algorithm to find common subsets

Question

I have N number of sets S_i of Numbers, each of a different size. Let m₁, m₂, ... m_n be the sizes of respective sets (m_i = | S_i |), and M be the size of the largest set. I have to find common subsets that have at least two numbers in them. Example:

Set  Items
1    10,80,22
2    72, 10, 80, 26,50
3    80,
4    10, 22
5    22, 72, 10, 80, 26,50

So the result will be like that

Items                Found in sets
10, 22               1, 4
10, 80               1, 2, 5
10, 80, 22           1, 5
10, 72, 80, 26, 50   2, 5

So how to automate this problem and what is the expected complexity for respective solution? I need it to be as fast as possible.

Answer 1

Since the original question asks to make a discussion as fast as possible, here's how it can be made short.

First, discuss whether the output is exponential to your input. Assume you have 2 elements, and N sets. Assume that each element belongs to each set; it will require N lines as your input. Then, how many lines should you print?

I think that you're going to print 2^N-N-1 lines, like these:

1,2     1,2
1,2     1,3
.....
1,2     1,N
1,2     2,1
.....
1,2     1,2,3
.....
1,2     1,2,3,...N

Since you're going to spend O(2^N) time printing, you could pick any of the suggestions on this page to calculate this information—you've been caught by an exponent anyway.

This argument would make your discussion very fast.