On May 25, 3:51 pm, [EMAIL PROTECTED] 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. -- http://mail.python.org/mailman/listinfo/python-list
