set partition question

[Arnaud Delobelle]

pball.benetech at gmail.com writes:

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

Unless your sets have some sort of pattern, it sounds to me like this
problem is at least exponential...  Good luck!

-- 
Arnaud