# Algorithm: Create groups from sets of nodes

I have a list of sets (a,b,c,d,e in below example). Each of the sets contains a list of nodes in that set (1-6 below). I was wondering that there probably is a general known algorithm for achieving the below, and I just do not know about it.

``````sets[
a[1,2,5,6],
b[1,4,5],
c[1,2,5],
d[2,5],
e[1,6],
]
``````

I would like to generate a new structure, a list of groups, with each group having

• all the (sub)sets of nodes that appear in multiple sets
• references to the original sets those nodes belong to

So the above data would become (order of groups irrelevant).

``````group1{nodes[2,5],sets[a,c,e]}
group2{nodes[1,2,5],sets[a,c]}
group3{nodes[1,6],sets[a,e]}
group4{nodes[1,5],sets[a,b,c]}
``````

I am assuming I can get the data in as an array/object structure and manipulate that, and then spit the resulting structure out in whatever format needed.

It would be a plus if:

• all groups had a minimum of 2 nodes and 2 sets.
• when a subset of nodes is contained in a bigger set that forms a group, then only the bigger set gets a group: in this example, nodes 1,2 do not have a group of their own since all the sets they have in common already appear in group2.

(The sets are stored in XML, which I have also managed to convert to JSON so far, but this is irrelevant. I can understand procedural (pseudo)code but also something like a skeleton in XSLT or Scala could help to get started, I guess.)

This was a post at StackOverflow. Answer is there.