On Mon, Apr 08, 2013 at 08:13:21PM -0400, Stavros Macrakis wrote:
> Henry, thanks for the term "atoms"
> .
>
>
> I'm not sure how I'd apply the disjoint-set data structure (union-find)
> here, but its dual partition
> refinement<http://en.wikipedia.org/wiki/Partition_refinement>looks
> relevant. That is linear in the size of the universe, but needs to
> be repeated for all the sets in S.
>
Hm, don't see how to apply that.
> Oliver, the equivalence relation (sets containing x) = (sets containing y)
> is conceptually very clean and simple, but I'm not sure what an efficient
> implementation would look like....
>
> Thanks again,
>
A simple-minded implementation is as follows:
First we need array-access. That is, we have an array
S[1], ..., S[m] of sets, where the elements are 1,...,n.
This needed to be done for any efficient algorithm, I guess.
Then we need to compute the array O[1], ..., O[n] of sets of
"occurrences", that is, O[i] is the set of j in {1,...,m} such that i is
in S[j]. These sets I would also guess are needed in any case.
The O-array is simply computed by running through i = 1 ... m,
and running through the elements j of S[i], and adding i to O[j].
One could optimise here the set-datastructure for the O[i].
Finally we need to lump together equal O[i]. This can be done by sorting
the O-array. Then running through the sorted O-array, one reads off the
D-sets in the obvious way (collecting all equal, now neighbouring,
indices).
Oliver
>
> On Mon, Apr 8, 2013 at 2:10 PM, Henry Baker <hbaker1 at pipeline.com> wrote:
>
> > Hi Stavros:
> >
> > I think these minimal sets are called 'atoms'.
> >
> > I believe that there are 'fast' (< quadratic) algorithms for this problem.
> >
> > At 08:11 AM 4/8/2013, Stavros Macrakis wrote:
> > >Given a set of sets S, what is the minimal set of disjoint sets D such
> > that each of the original sets is a union of elements of D?
> > >
> > >For example, if S = { {a,b,c,d,e}, {a,c}, {c,f,g} }, then D = { {a}, {c},
> > {f, g}, {b,d,e} }.
> > >
> > >What is the name of this problem?
> > >
> > >The obvious way to solve it is to calculate the full lattice of
> > intersections and set differences, but the straightforward way of doing
> > that seems computationally expensive. What are good algorithms for this
> > problem?
> > >