union/intersection of 2 sets, where each set are defined by it's subsets

Question

We know every set's definition from the union of other sets.

For example

A = B union {1,2}

B = C union D

C = {5,6}

D = {5,7}

E = {4}

then A = {1,2,5,6,7}

A union E = {1,2,4,5,6,7}

Are the any efficient algorithms to do that. Suppose the hierarchy of unions can be really deep, and the subsets can change pretty often(not that much). I think there should be ways to minimize reduce the amount of unions one have to make.

Answer 1

Perhaps you're looking for some sort of disjoint set data structure?

Answer 2

Several questions about this case.

First question: For how long does this "script" / "program" have to run? In case it's not too long, it could well be a good option to simply store previous unions and checking cache before performing a union action. Memory isn't that expensive nowadays :).

Second question you should ask: are elements in a certain order before union? If they aren't, and a list is accessed more than once, it can be very useful to sort a list first (than you can make a decision when you're only halfway a list, for example). Mergesort is a powerful technique of the efficient join of two ordered lists.

Answer 3

So you have a unchanging hierarchy of unions of changing sets? And you are, like in your example, only interested in the value of one set?

Then flatten the hierarchy. That is, in your example you would once walk through the hierarchy to find the set of changing sets your set is the union of, and store this set.

To dispense with recomputing unions whenever a leaf set changes, you could track for each element in how many sets it is currently contained. This can be updated quickly if a leaf set changes, and those not required looking at any unchanged leaf sets. Then, those elements with frequency count > 0 are currently in the union.