Oliver,
Thanks for the thoughts. Here is what I had earlier today:
atomic_sets(s):=
block([elements],
local(m),
m[q]:={},
for i in s do
for j in i do
m[j]: adjoin(i,m[j]),
elements: setify(xreduce('append,rest(arrayinfo(m),2))),
equiv_classes(elements,lambda([a,b],m[a]=m[b]))
);
Sorting, as you suggest, would speed up the last step from O(n^2) to O(n
log n) set comparisons.
-s
On Mon, Apr 8, 2013 at 11:48 PM, Oliver Kullmann
<O.Kullmann at swansea.ac.uk>wrote:
> 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?
> > > >
>
>