set partition question

[Arnaud Delobelle]

pball.benetech at gmail.com writes:

> On May 25, 1:13 pm, "Martin v. Löwis" <mar... at v.loewis.de> wrote:
>> > We can use any operation or function which
>> > takes and returns sets.
>>
>> I think the problem is significantly underspecified. It would be a more
>> interesting problem if there was a restriction to a few selected set
>> operations, e.g. union, intersection, difference, and combinations
>> thereof.
>
> Ok, that's quite right -- when I just tried to define "any function,"
> I found that all the solutions I came up with were combinations of the
> set operations defined for immutable sets. Let me improve the spec as
> the following:
>
> There may be arbitrarily many set elements (denoted by integers
> 1,2,3,...), arbitrarily many combinations of the elements composing
> the sets s_i (s0, s1, ...). We can use any of python's set operations
> or combination of those operations.

OK then, if you only allow union, intersection, difference, symmetric
difference then I think it would be easy to prove (I haven't done it!)
that if there is a solution to you problem, then the method below
yields a solution:

*** warning: all this is untested AND written in a rush ***

let S be the set of all your sets except s0 (i.e. s1, s2, s3, ...)


# X is the "domain", C is the set of complements in X of elements of S

X = reduce(set.union, S)
C = set(X - s for s in S)


# Find the "fibers" at each element x of s0.  A fiber at x is the set
# of all s in S or C that contain x

from collections import defaultdict
fibers = defaultdict(list)

for s in S | C:
    for x in s & s0:
        fibers[x].append(s)


# Find the "seeds" at each x in s0.  A seed at x is the set of all
# elements contained in all s in the fiber at x.

# Intutively, a seed at x is the smallest set containing x that can be
# built from S

seeds = [reduce(set.intersection, F) for F in fibers.itervalues()]


# Now we know if there is a solution:

sol = reduce(set.union, seeds)

if sol != s0:
    print "No solution"
else:
    print "Solution: union(intersection(fibers[x]) for x in s0)"


I think this solution will be found in O(m*n**2) time, where:

* n is the size of X (i.e. the total number of elements)
* m is the size of S (i.e. the total number of sets)

and assuming that set operations are linear.

-- 
Arnaud