Python Forum

Python Forum > General > Code sharing > a solution to the Subset Sum Problem
Full Version: a solution to the Subset Sum Problem
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2

league55

Jan-15-2018, 02:56 AM
(The Subset Sum Problem involves determining whether any combination of the elements of a set of integers adds up to zero. For example, for the set {-3, 0, 2, 5, 7, 13} the solution is {-3, 13). For {-4, -3, 1} there is no solution. The problem is considered np-complete. One of the things that means is that you have to test every possible, unique combination of elements in order to determine that the problem has no solution.)

Someone kindly provided me with an algorithm that attempts to solve the Subset Sum Problem, so I thought I'd share it here. This algorithm takes advantage of the fact that you don't necessarily have to test every possible, unique combination in order to find the solution, if there is a solution; and it takes advantage of that fact with clever use of generators.

from itertools import combinations

def solve(input):
    subsets = (
        subset for length in range(1, len(input))
        for subset in combinations(input, length)
    )
    solution = next((subset for subset in subsets if sum(subset) == 0), None)
    if solution is None:
        print('There is no solution for set {}.'.format(input))
    else:
        print('A solution for set {} is {}.'.format(input, solution))

sparkz_alot

Jan-15-2018, 02:13 PM
Interesting, but I will say that "input" is a terrible name for a variable, since it is a function in Python.

league55

Jan-15-2018, 02:58 PM
(Jan-15-2018, 02:13 PM)sparkz_alot Wrote: [ -> ]Interesting, but I will say that "input" is a terrible name for a variable, since it is a function in Python.

Does input the variable mask input() the function and make it inaccessible? I didn't know!

sparkz_alot

Jan-15-2018, 03:28 PM
At the very least, following that practice leads to confusion. It is always best, in any programming language, to stay away from naming your variables after keywords or functions of that language. If you must do it, better to alter it in someway, for example "my_input" rather than "input", thereby eliminating the possibility.

Gribouillis

Jan-16-2018, 07:30 AM
For me, this is an overuse of generator expressions. When they are not needed, it is better (and it may actually be faster) to write ordinary syntax like so
from itertools import combinations

def solve(items):
    for length in range(1, len(items)):
        for subset in combinations(items, length):
            if sum(subset) == 0:
                print('A solution for set {} is {}'.format(items, subset))
                return
    print('There is no solution for set {}'.format(items))

if __name__ == '__main__':
    solve({-3, -10, 2, 5, 7, 13})
Generator expressions are most useful when you want to create and manipulate 'sequences' of things.

Skaperen

Jan-24-2018, 04:56 AM
i've been having trouble understanding how the set {-3, 13} adds up to zero, unless this is all modulo 10.

league55

Jan-24-2018, 06:15 AM
(Jan-24-2018, 04:56 AM)Skaperen Wrote: [ -> ]i've been having trouble understanding how the set {-3, 13} adds up to zero, unless this is all modulo 10.

It's decimal numbers, or standard ints.

I suppose the snippet could be rewritten to make the numeric base a variable.

Mekire

Jan-24-2018, 03:13 PM
I want to point out that this is actually a pretty bad way to solve subset sum.
First generalize the problem to trying to sum to a specified target rather than zero. We can do this WLOG by just adding the absolute minimum value to every item.

The standard DP approach is much more efficient and isn't based on just iterating through combos hoping for a hit.

Let T[i,j] be a boolean representing whether the first i items of our sequence can sum to j.
This gives the recursive formulation:
if j >= ith value:
    T[i,j] = T[i-1, j-value] or T[i-1, j]
else:
    T[i,j] = T[i-1, j]
Fill in the table row by row:
import numpy as np

def subset_sum(sequence, target):
    T = np.zeros((len(sequence)+1, target+1), dtype=int)
    T[:,0] = 1 
    for i,num in enumerate(sequence, start=1):
        for j in range(1, target+1):
            if j >= num:
                T[i,j] = T[i-1, j-num] or T[i-1, j]
            else:
                T[i,j] = T[i-1, j]
    return T
We can then reconstruct the set from this table (could be cleaned up a bit):
def subset_sum_solution(sequence, target):
    T = subset_sum(sequence, target)
    n = len(sequence)
    solution = []
    if T[n,target]:
        while n > 0 and target > 0:
            if not T[n-1, target]:
                solution.append(sequence[n-1])
                target -= sequence[n-1]
            n -= 1
    return solution
Now lets create a big enough problem so we can see the difference in efficiency:
Hide/Show
If you try this with your program (you will have to alter it to sum to a target instead of zero which is simple), you will find yours takes quite a lot longer. More than this though, if hypothetically there was no such solution, the DP version would still take the same time; whereas yours might approach the heat death of the universe.

Of course the DP version is still not polynomial in the input size of the problem (it is what we call psuedo-polynomial).

Skaperen

Jan-25-2018, 03:51 AM
(Jan-24-2018, 06:15 AM)league55 Wrote: [ -> ]
(Jan-24-2018, 04:56 AM)Skaperen Wrote: [ -> ]i've been having trouble understanding how the set {-3, 13} adds up to zero, unless this is all modulo 10.

It's decimal numbers, or standard ints.

I suppose the snippet could be rewritten to make the numeric base a variable.

even in standard ints -3 + 13 != 0

or what am i miss(\bunderstand)ing?

Mekire

Jan-25-2018, 06:27 AM
Occam's Typo. He meant to write -13.
Pages: 1 2
Python Forum > General > Code sharing > a solution to the Subset Sum Problem