set partition question

[pball.benetech at gmail.com]

dear pythonistas,

So imagine that we have a set of sets S. If we pick arbitrarily one
set, s0, what are all the combinations of other sets in S which when
combined by set operations result in s0?

s0 = set([1])
s1 = set([1,2])
s2 = set([2])
S = set([s0,s1,s2])
one answer we're searching for is s0 = s1 - s2

There may be arbitrarily many set elements (denoted by integers
1,2,3,...) and arbitrarily many combinations of the elements composing
the sets s_i (s0, s1, ...). We can use any operation or function which
takes and returns sets.

I think this problem is related to integer partitioning, but it's not
quite the same. The range of answers has a little combinatorial
explosion problem as S gains new members. In my problem, len(S) is
usually on the order of 1M, and in the worst case, 10M, and there are
on the order of 10k elements.

My attempts to come up with an algorithm have not succeeded. Any ideas
occur to you folks? -- PB.

--
Patrick Ball, Ph.D.
Chief Scientist
   & Director, Human Rights Program
http://www.benetech.org
http://www.hrdag.org
http://www.martus.org