Python Forum
a solution to the Subset Sum Problem
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
a solution to the Subset Sum Problem
#1
(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))
Reply
#2
Interesting, but I will say that "input" is a terrible name for a variable, since it is a function in Python.
If it ain't broke, I just haven't gotten to it yet.
OS: Windows 10, openSuse 42.3, freeBSD 11, Raspian "Stretch"
Python 3.6.5, IDE: PyCharm 2018 Community Edition
Reply
#3
(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!
Reply
#4
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.
If it ain't broke, I just haven't gotten to it yet.
OS: Windows 10, openSuse 42.3, freeBSD 11, Raspian "Stretch"
Python 3.6.5, IDE: PyCharm 2018 Community Edition
Reply
#5
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.
Reply
#6
i've been having trouble understanding how the set {-3, 13} adds up to zero, unless this is all modulo 10.
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#7
(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.
Reply
#8
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:
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).
Reply
#9
(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?
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#10
Occam's Typo. He meant to write -13.
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020