set partition question

[Arnaud Delobelle]

pball.benetech at gmail.com writes:

> I used Arnaud's suggestion with a few minor tweaks, as follows:
>
> #-----
> fset = frozenset
> s0 = fset([1])
> s1 = fset([1,2])
> s2 = fset([2])
>
> # let S be the set of all your sets except s0 (i.e. s1, s2, s3, ...)
> S = set([s1,s2])
>
> # X is the "domain", C is the set of complements in X of elements of
> S
> X = set()
> for s in S:
>     X |= s
> print "s0 is ", s0
> print "S is ", S
> print "X is ", X
>
> C = set(fset(X - s) for s in S if fset(X-s))
> print "C is ", C
>
> # 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)
> print "fibers are ", fibers
>
> # 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 = set()
> for F in fibers.itervalues():
>     seeds &= set(F)
Change this to:

seeds = []
for F in fibers.itervalues():
    seed = X
    for f in F:
        seed &= f
    seeds.append(seed)

And the whole thing should work

HTH

> print 'seeds are ', seeds
>
> # Now we know if there is a solution:
> sol = set()
> for s in seeds:
>     sol |= s
> if sol != s0:
>     print "No solution"
> else:
>     print "Solution: union(intersection(fibers[x]) for x in s0)"
> #-----
>
> yields this:
>
> s0 is frozenset([1])
> S is  set([frozenset([1, 2]), frozenset([2])])
> X is  set([1, 2])
> C is  set([frozenset([1])])
> fibers are  defaultdict(<type 'list'>, {1: [frozenset([1, 2]),
> frozenset([1])]})
> seeds are  set([])
> No solution
>
>
> I follow your logic up to the point of the "seeds," where I get a bit
> confused. Thanks much! for the idea, I'm going to keep thinking about
> it. Any other ideas are *most* welcome. -- PB.

-- 
Arnaud