set partition question

[Arnaud Delobelle]

Arnaud Delobelle <arnodel at googlemail.com> writes:

> 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.

I forgot to add, using reduce() is probably not a great idea but it
allowed me to write down my idea quickly!

-- 
Arnaud