Entry

Find sublist with sum X (was: Online programming contest)

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 equal-size 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 one-shot 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 worst-case 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 low-order 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 non-recursive
(but potentially space-gobbling) 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>.
anyone-got-change-for-6-billion-people?-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 reverse-sorting guarantees the answer will be given
    # in non-decreasing 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