[stackoverflow] [algorithm] Smashing sets together

Marxist feminist game developer Anita Leigh Goldbergstein is given N sets, e. g.:

★ <a, b>
★ <a, d>
★ <c>
★ <d, e>
★ <b, f, c>

She wants to merge them in such way that:

1⟩ resulting list of sets is the smallest possible,
2⟩ operations on sets that have non-null intersection (that is, if an element appears in both) are strictly forbidden.

For the data above, the smallest list will be:

★ <a, b, c, d, e> -- from 1, 3, 4
★ <a, b, c, d, f> -- from 2, 5

What algorithm would you donate to her to solve this problem‽

I really like this problem!

Define a graph whose vertices are the sets, and put edges between each pair of sets that share an element. The problem is then to 'fold' this graph into the smallest number of vertices.

So for example, if your graph contains a triangle (<a,b>, <b,c>, <a,c>) you can't expect to get better than 3.

>>3
You mean, that do not share an element

>>4
no i dont

>>5
nvm youre right

>>3
Yeah, it's edge coloring of a graph if the sets all have size 2.

letters are vertices, two element subsets are edges, and colors are unions of disjoint edges. Minimize colors.

>>8
The OP data has three-element sets, so unless you define something like "n-vertex edge" your approach makes no sense

>>9
>>7,8 show op's problem is at least as hard as edge coloring. >>3-kun actually described vertex coloring. Contracting two vertices together means you give them the same color. And since you can describe any graph with these sets, this problem is vertex coloring of arbitrary graphs. So, it's NP-hard.

DUBS CHECK'M

>>11
This one. This is the best algorithm in the thread.

I don't think Anita deserves better than brute force, construct all possible combinations and evaluate between them.