Algorithm for calculating all intersects and disjoints for an indefinite
number of sets
Recently I had to develop a nieve recursive algorithm for the set problem
outlined below, but would now like to know what the formal
description/name of the problem is and whether there's an algorithm that
allows the problem to be solved more efficiently (I suspect there is).
I know there are separate algorithms for finding intersects and disjoints,
but I haven't recognized any that cover this problem as a whole.
The problem:
To take an indefinite number of sets and return one set for each intersect
and non-intersect of all the sets.
For example, given 4 sets as input A,B,C,D:
A {1,14,2,10,13,12,8,9}
B {2,3,14,15,11,13,9}
C {13,10,4,15,5,6,12,11}
D {7,8,9,13,11,6,12}
The result should be the following 13 sets:
{1,14},{2},{3},{4,15},{5},{6},{7},{8},{9},{10},{11},{12},{13}
The algorithm I developed was nieve in that it compared all set
permutations recursively (I wanted to be able to implement this relatively
easily in XSLT 2.0) until no further intersects were found.
Some context, I needed to perform this operation to describe how multiple
versions of a tree modify the original tree, at each point on the tree.
The 'tree' is actually an XML document.
No comments:
Post a Comment