
+ Search 

Jul 5th, 2000 10:03
Nathan Wallace, Hans Nowak, Snippet 318, Tim Peters
""" Packages: maths """ """ > ... > My algortihm (not shown) would be recursive up to depth n (given n > numbers). Any ideas what depth of recursion the contest would allow? No idea. > What depth of recursion is a reasonable limit to aim for in Python? At least thousands. > My guess is that given n numbers, brute force is O(2^n) and O(2^(n/2)) > should be attainable. Any math experts have the real answers? Yes, O(2^(n/2)) is attainable: split the list in equalsize halves A and B, compute all possible sums from A (O(2^(n/2))) and B (ditto) separately, then see whether there's a sum from A and a sum from B that have the desired total (again O(2^(n/2)) using e.g. a hash table). Note that this is a oneshot trick, though: it breaks the problem into two subproblems of a *different* nature, so it's the end of that road. I don't know of a better worstcase general solution than that. Agree with Aaron it's a hard problem; disagree that it's 0/1 knapsack in disguise (which is about maximizing a linear function, not about hitting a specific value on the nose); it *is* an instance of the "sum of subsets" problem family, though. The attached solves a slightly more general problem and usually works well in "real life" problems (more like loworder polynomial time than exponential, although its worst case in contrived examples is indeed O(2^n)). The same bounding functions (for weeding out impossibilities) can be used in a recursive framework that requires no more than O(n) space; but since the approach does work so well in real life, and frequent recursion is relatively very expensive in Python, I use this nonrecursive (but potentially spacegobbling) version. Note that this approach buys some of its efficiency at the cost of being hard to extend to find *all* solutions. That's easy in a straightforward recursive version, though  so use that if you're trying to teach the neighborhood supermarket checkout droid all the unseen possibilities open to them for making correct change <wink>. anyonegotchangefor6billionpeople?ly y'rs  tim """ def find_sublist_with_sum(nlist, target): """Return sublist of nlist whose elements add up to target. Return None if no such sublist exists. The return value never contains 0. The return value is [] if target is 0. The order of elements in the return value is not defined. If more than one sublist sums to target, which one is returned is not defined. Examples: xxx([1, 2, 3], 3) == [1, 2] or [2, 1] or [3] xxx([2, 1, 1, 0, 0], 0) == [] xxx([2, 1, 1, 0, 0], 1) == [1] xxx([1, 2], 8) == None xxx([1, 2, 3, 4], 6) == [1, 2, 3] or [2, 4] or etc """ # Sort to help the bounds checks cut off impossibilities early; # not needed for correctness, and other ordering strategies may # be more helpful depending on the expected cases. # Note that reversesorting guarantees the answer will be given # in nondecreasing order. ns = nlist[:] ns.sort() ns.reverse() # find smallest and largest possible sums max_left = min_left = 0 for n in ns: if n >= 0: max_left = max_left + n else: min_left = min_left + n # map partial sum to last element added into it partial = {0: 0} inpartial = partial.has_key # instrumentation global _nconsidered, _nsurvivors # Each iteration of the outer loop leaves partial containing # all distinct possible sums taken from sublists ending at n. # Except that some of those are trash: if a partial sum plus # min_left is greater than target, all possible completions # are greater than target, so that partial sum can be ignored; # similarly if a partial sum plus max_left is less than target. for n in ns: if n >= 0: max_left = max_left  n else: min_left = min_left  n for sum in partial.keys(): _nconsidered = _nconsidered + 1 this = sum + n if min_left <= target  this <= max_left and \ not inpartial(this): _nsurvivors = _nsurvivors + 1 partial[this] = n if this == target: return _construct_sublist(partial, target) assert min_left == max_left == 0 return None def _construct_sublist(partial, target): answer = [] while target: n = partial[target] answer.append(n) target = target  n return answer _nconsidered = _nsurvivors = 0