set partition question

[pball.benetech at gmail.com]

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