set partition question

[miller.paul.w at gmail.com]

On May 25, 3:51 pm, pball.benet... at gmail.com wrote:
> dear pythonistas,
>
> 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.

If, by "integer partitioning," you mean the "subset sum
problem" (given a finite set S of integers, does S contain a subset
which sums up to some given integer k?), then you are right.  I'm
reasonably sure there's a polynomial reduction from your problem to
the subset sum problem.  That would make your problem NP-complete.

As for algorithms, I don't think there's an exact algorithm any better
than trying all the possibilities and stopping when one comes close.
Say, for example, we specify the problem to be: given sets s_0, s_1,
s_2, ..., s_n, with S defined to be the union of all the s_i's, return
all functions f which, using the sets s_1, s_2, ..., s_n and the
elementary set operations (union, intersection, difference), returns
the set s_0.

Now, you need to be a little more careful, because, given a function f
which satisfies the problem, I can always define f' = f(S) + s_1 - s_1
and get another function which satisfies the definition.

Like I said, because this looks related to the subset sum problem
(though harder, because you're asking for "all" such functions, for
some rigorous definition of "all," as per the previous sentence), I
suspect it's NP-complete.  However, there are probably some good
heuristics, such as if s1 has a large intersection with s0, it's
probably a good idea to use s1 in whatever formula you come up with.

Other than that, I don't really have an idea.  Can you say what the
application of this algorithm would be?  Knowing the use case might
suggest a better approach.